堆（大顶堆）的概念
堆是一种特殊的二叉树，大顶堆就是根节点为最大值的堆，它具有如下的特点：
- 堆是完全二叉树
- 堆常用数组来实现，也可以用树来实现。
- 堆中的每个节点都满足堆的条件：每个节点的关键字都大于（或等于）它的子节点的关键字
完全二叉树：就是指除了最后一层可能不是满节点，其他各层都必须是满节点的树，最后一层的节点遍布在树的左侧。
这个概念理解起来有点困难，但有一个简单的判断标准：一个完全二叉树对应一个没有空洞的数组，如下图所示
完全二叉树与非完全二叉树对应数组.jpg
画了一个极丑的图，凑活着看一下，意思就是非完全二叉树（下图）对应的数组下标8的元素为空洞（对应各种数据类型初始值，这里以空白表示），而一个完全二叉树（上图），其实就是一个大顶堆，满足堆的三个特点，对应了一个没有空洞的数组，这张图也反映了堆与数组的对应关系。
堆的特性与方法
弱序：堆相比于二叉搜索树是弱序的，二叉搜索树每个节点的左子结点的关键字都小于右子节点的关键字，但是堆每个节点的两个子节点关键字大小并无关系，只是约束为小于父节点关键字。
由于堆是弱序的，决定了一些方法是困难的或者无法实现的，比如说遍历、查找，这里所说的遍历和查找是按照树的特性来遍历和查找，时间复杂度为O(logN)。当然如果线性遍历查找对应数组也可以实现遍历和查找的功能，但时间复杂度降为O(N)。
虽然堆是弱序的，但对快速移除最大节点和快速插入新节点来说已经足够了，文章最后将给出堆的时间复杂度，我们先来看一下堆的操作。
移除：由于堆的最大值在根节点，移除最大节点的操作就很简单
maxNode = heapArray[0];
但问题在于移除之后，堆的结构就被破坏了，如何再构建出一个新的堆呢，这个操作叫做下滤
下滤：下滤操作分为三部分
1.把堆的最后一个节点移动到根节点，填补根节点被移除的空洞，称为index节点，数组容量减一
2.比较index节点的两个子节点的关键字，选出值较大的那个节点，称为larger节点，如果只有一个子节点，那就不用比较，直接为larger节点
3.比较index节点与larger节点的关键字，如果index<larger就交换两个节点位置，然后重复步骤2
简单点来说就是先用最后一个节点填补根的空洞（选用最后一个节点是为了保证为一个完全二叉树），然后经过比较把这个节点“沉”到合适的位置：小于父节点大于子节点，即满足堆的特点，这样就又构造了一个堆，结合图来看会比较容易理解。
我又要画图了...
下滤操作示意图.png
插入：将新的节点插入堆的最后，然后通过上滤操作，将新节点“升”到合适的位置
heapArray[N] = newNode;
N++;
上滤：上滤操作相比于下滤操作稍简单些，因为向上构建的话父节点就一个，不用像下滤一样比较两个子节点的关键字大小。
方法：比较新节点与父节点的关键字大小，如果新节点的关键字比较大就交换位置，直到上升到一个合适的位置，比父节点小比子节点大，这样又构建成了一个新的堆。
上滤操作就不画图了，反过来看就行了。
注意：这里上滤和下滤中的交换并不是真的交换（调用swap方法），一次交换需要复制三次数据，因为堆的上滤和下滤的方法具有流动性，可以先把比较的节点拿出来空出位置，这样被比较的节点可以流动填补空缺，最后再将拿出来的节点放回合适的位置，这样可以节省多次复制的操作。可以类比于排序算法中的冒泡和插入，冒泡是需要两两相比较，然后可能会交换位置，而插入排序实现则把待插入的数据拿出来，被比较的数流动填补空洞，最后插入合适的位置，一般来说这会比冒泡排序少了很多次数据复制过程，毕竟能省一点是一点。
堆的实现代码
下面展示堆的实现代码，有三个类，数据节点类，堆的实现方法类还有一个用于测试的App类
在分析代码之前需要先了解堆这个结构中，父节点和两个子节点的关系：
已知父节点对应的数组下标为x，则它的两个子节点对应的数组下标分别为：
左子结点：2x + 1 右子节点：2x + 2
已知一个子节点的数组下标为x，则它的父节点对应的数组下标为：
父节点：(x-1)/2
首先构建一个Node类，代表节点对象，简单起见，Node类就一个整型变量data
public class Node {
//关键字
private int data;
//getter and setter
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
//构造方法
public Node(int data) {
this.data = data;
}
}
Heap类，这个是主要实现堆的类：
public class Heap {
//对应数组、数组的最大容量、元素个数
private Node[] heapArray;
private int maxSize;
private int currentSize;
//构造方法，传入数组最大容量，构造数组，元素个数初始值为0
public Heap(int maxSize) {
this.maxSize = maxSize;
currentSize = 0;
heapArray = new Node[maxSize];
}
//判断堆是否为空的方法，为remove方法准备
public boolean isEmpty() {
return (currentSize == 0);
}
//插入方法中调用上滤的方法
public boolean insert(int key) {
if (currentSize == maxSize) {
return false;
}
Node newNode = new Node(key);
heapArray[currentSize] = newNode;
trickleUp(currentSize++);
return true;
}
//上滤方法，注意while循环体的条件一定是index>0，如果index=0则会导致parent求值后数组越界
public void trickleUp(int index) {
Node newNode = heapArray[index]; //新插入的节点
int parent = (index-1)/2; //index对应节点的父节点下标
while(index > 0 && heapArray[parent].getData() < newNode.getData()) {
heapArray[index] = heapArray[parent]; //如果parent关键字小则"下沉"
index = parent; //index指针向上移动
parent = (parent-1)/2; //相应的parent指针也向上移动
}
heapArray[index] = newNode; //最后将插入的节点填补到合适的位置
}
//移除方法，调用下滤方法完成堆的重构
public Node remove() {
if (isEmpty()) {
return null;
}
Node root = heapArray[0];
heapArray[0] = heapArray[--currentSize];
trickleDown(0);
return root;
}
//下滤方法，while循环体的条件index < currentSize/2是筛选出至少有一个子节点的节点(如果是有一个子节点那一定是左子节点)
public void trickleDown(int index) {
int largerChild; //变量指向两个子节点中关键值较大的那个
Node top = heapArray[index]; //先把新的根节点拿出来，新的根节点为之前堆的最后一个节点
while (index < currentSize/2) { //循环向下探测
int leftChild = 2*index + 1; //左子节点的下标
int rightChild = leftChild + 1; //右子节点的下标
//if中第一个条件确定右子节点否存在，第二个条件比较左右两个子节点的大小，找到较大的那一个
if (rightChild < currentSize && heapArray[leftChild].getData() < heapArray[rightChild].getData()) {
largerChild = rightChild;
} else {
largerChild = leftChild;
}
//再比较根节点与较大那个子节点的关键值大小，满足条件则移动位置
if (top.getData() >= heapArray[largerChild].getData() ) {
break;
} else {
heapArray[index] = heapArray[largerChild];
index = largerChild;
}
}
//最后将拿出来的新根节点插入到合适的位置
heapArray[index] = top;
}
//一个打印堆的方法，让堆显示出来更像一颗二叉树
public void displayHeap() {
System.out.printf("heapArray: ");
for (int j = 0; j < currentSize; j++) {
if (heapArray[j] != null) {
System.out.printf(heapArray[j].getData() + " ");
} else {
System.out.printf("-- ");
}
}
System.out.println();
int nBlanks = 32;
int itemsPerRow = 1;
int column = 0;
int j = 0;
String dots = "..................................";
System.out.println(dots + dots);
while (currentSize > 0) {
if (column == 0) {
for (int k = 0; k < nBlanks; k++) {
System.out.print(" ");
}
}
System.out.print(heapArray[j].getData());
if (++j == currentSize) break;
if (++column == itemsPerRow) {
nBlanks /= 2;
itemsPerRow *= 2;
column = 0;
System.out.println();
} else {
for (int k = 0; k < nBlanks*2 - 2; k++) {
System.out.print(" ");
}
}
}
System.out.println("\n" + dots + dots);
}
}
最后是一个app测试类，用来演示验证堆的各种方法，HeapApp类：
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class HeapApp {
public static void main(String[] args) throws IOException{
int value;
Heap theHeap = new Heap(31); //构造一个最大容量为31的堆
boolean success;
//向堆中插入测试数据
theHeap.insert(10);
theHeap.insert(20);
theHeap.insert(30);
theHeap.insert(40);
theHeap.insert(50);
theHeap.insert(60);
theHeap.insert(70);
theHeap.insert(80);
theHeap.insert(90);
//提供一个方法入口，用户可以通过输入首字母来对创建的堆进行操作
while (true) {
System.out.print("Enter first letter of show, insert, remove, change: ");
int choice = getChar();
switch (choice) {
case 's': //打印堆
theHeap.displayHeap();
break;
case 'i': //向堆中插入数据
System.out.print("Enter value to insert: ");
value = getInt();
success = theHeap.insert(value);
if (!success) {
System.out.println("Can't insert, heap full");
}
break;
case 'r': //从堆中移除数据
if (!theHeap.isEmpty()) {
theHeap.remove();
} else {
System.out.println("Can't remove;, heap empty");
}
break;
default:
System.out.println("Invalid entry\n");
}
}
}
public static String getString() throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
public static char getChar() throws IOException {
String s = getString();
return s.charAt(0);
}
public static int getInt() throws IOException {
String s = getString();
return Integer.parseInt(s);
}
}
运行这个程序结果，如下图所示：
堆示例的运行结果.png
堆的效率
堆的操作耗时基本都在上滤和下滤操作的循环方法中，复制操作的次数为树的高度减一，设树的高度为H，则树高与节点数N的关系为：H=log2(N+1)，复制次数为：H-1，所以去掉常数，堆操作的时间复杂度为O(logN)
堆排序
基于对以上堆的理解，再来分析堆排序就会相对简单
设想：将一个乱序的数组中的所有元素，调用堆的insert()方法插入堆中，再调用堆的remove()方法逐个返回堆顶元素，这样就可以得到一个有序的数组。
因为insert()和remove()方法的时间复杂度都是O(logN)，且都需要执行N次，则堆排序算法的时间复杂度为O(N*logN)
以上的设想是基于我们已经实现了一个堆，将堆作为一个工具来对数组进行排序，但堆作为一个ADT（抽象数据结构），它的底层也是一个数组，是不是可以考虑在待排序的数组之上直接构建堆，这样可以省去一个数组的内存空间。
将一个乱序的数组构建为一个堆，有两种方法：
- 可以对数组中的元素遍历调用上滤trickleUp()的方法，这样总共调用了N次上滤的方法，时间复杂度还是O(N*logN)
- 但如果换一种思路，采取下滤trickleDown()的方法来构建堆，哪些元素需要下滤呢，有子节点的节点需要下滤，那么所有的叶子节点就可以不用考虑，这样平均是调用了N/2次下滤的方法，虽然总的时间复杂度依然是O(N*logN)，但还是要快一些，下面用一组简单极丑的图来说明一下：
数组构建堆的方法比较.png
上图中左图采用方法1，右图采用方法2，可以清晰的观察到右图的效率更高
以下代码我们采用方法2下滤的方式构建堆
堆排序的实现代码
首先实现构建堆的代码，传入一个数组，方法仅需要考虑remove()和trickleDown()方法的实现，外加打印堆和数组的方法：
class Heap {
//传入数组，构建成堆
public void build2Heap(int[] arr) {
int size = arr.length;
//j的初始值对应最后一个有子节点的节点，然后开始下滤操作
for (int j = size/2 - 1; j >= 0; j--) {
trickleDown(arr,size,j);
}
}
//下滤操作没有什么变化，注意循环条件和判断条件即可
public void trickleDown(int[] arr, int size, int index) {
int largerChild;
int current = arr[index];
while (index < size/2) {
int leftChild = index*2 + 1;
int rightChild = leftChild + 1;
if (rightChild <= size && arr[rightChild] > arr[leftChild]) {
largerChild = rightChild;
} else {
largerChild = leftChild;
}
if (current > arr[largerChild]) {
break;
} else {
arr[index] = arr[largerChild];
index = largerChild;
}
}
arr[index] = current;
}
//remove操作注意传入数组的size已经截取有序的部分
public int remove(int[] arr, int size) {
int top = arr[0];
arr[0] = arr[--size];
trickleDown(arr, size, 0);
return top;
}
//用树的形式来打印堆的方法
public void displayHeap(int[] arr) {
int size = arr.length;
int nBlanks = 32;
int itemsPerRow = 1;
int column = 0;
int j = 0;
String dots = "..................................";
System.out.println(dots + dots);
while (size > 0) {
if (column == 0) {
for (int k = 0; k < nBlanks; k++) {
System.out.print(" ");
}
}
System.out.print(arr[j]);
if (++j == size) break;
if (++column == itemsPerRow) {
nBlanks /= 2;
itemsPerRow *= 2;
column = 0;
System.out.println();
} else {
for (int k = 0; k < nBlanks*2 - 2; k++) {
System.out.print(" ");
}
}
}
System.out.println("\n" + dots + dots);
}
//打印堆对应数组的方法
public void displayArray(int[] arr) {
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[j] + " ");
}
System.out.println();
}
}
以上堆的操作中省略了insert()方法和trickleUp()方法，因为采用方法2的堆排序用不到这些方法
HeapSort类主要在heapSort()方法中实现了将数组构建成堆，然后再调用堆的remove()方法得到有序数组
下面直接给出全部堆排序的代码，上面的Heap部分是其中的一个内部类，HeapSort：
public class HeapSort {
private int[] arr;
//构造方法，传入数组
public HeapSort(int[] arr) {
this.arr = arr;
}
//堆排序的方法
public void heapSort() {
int size = arr.length;
int currentSize = size; //currentSize初始值为数组长度
int j;
System.out.print("unSorted: "); //先打印出未排序的数组
displayArr(arr);
Heap theHeap = new Heap(); //创建一个堆对象
theHeap.build2Heap(arr); //构建堆
System.out.print("Heap: "); //打印堆与对应数组
theHeap.displayArray(arr);
theHeap.displayHeap(arr);
//堆构建完成后，通过remove方法来得到有序数组
//这里注意只有一个数组，取出来的最大值放在哪里呢？正好堆重新构建后，数组的最后一位空出来了
//我们可以合理利用空间，将最大值循环的插入数组最后
for (j = size-1; j>=0; j--) {
int biggest = theHeap.remove(arr,currentSize--); //这里传入的currentSize已经将有序部分截断了
arr[j] = biggest;
}
//打印排序之后的数组
System.out.print("Sorted: ");
displayArr(arr);
}
//打印数组的方法
public void displayArr(int[] arr) {
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[j] + " ");
}
System.out.println();
}
//内部类，堆的实现
class Heap {
//传入数组，构建成堆
public void build2Heap(int[] arr) {
int size = arr.length;
//j的初始值对应最后一个有子节点的节点，然后开始下滤操作
for (int j = size/2 - 1; j >= 0; j--) {
trickleDown(arr,size,j);
}
}
//下滤操作没有什么变化，注意循环条件和判断条件即可
public void trickleDown(int[] arr, int size, int index) {
int largerChild;
int current = arr[index];
while (index < size/2) {
int leftChild = index*2 + 1;
int rightChild = leftChild + 1;
if (rightChild <= size && arr[rightChild] > arr[leftChild]) {
largerChild = rightChild;
} else {
largerChild = leftChild;
}
if (current > arr[largerChild]) {
break;
} else {
arr[index] = arr[largerChild];
index = largerChild;
}
}
arr[index] = current;
}
//remove操作注意传入数组的size其实已经截取有序的部分
public int remove(int[] arr, int size) {
int top = arr[0];
arr[0] = arr[--size];
trickleDown(arr, size, 0);
return top;
}
//用树的形式来打印堆的方法
public void displayHeap(int[] arr) {
int size = arr.length;
int nBlanks = 32;
int itemsPerRow = 1;
int column = 0;
int j = 0;
String dots = "..................................";
System.out.println(dots + dots);
while (size > 0) {
if (column == 0) {
for (int k = 0; k < nBlanks; k++) {
System.out.print(" ");
}
}
System.out.print(arr[j]);
if (++j == size) break;
if (++column == itemsPerRow) {
nBlanks /= 2;
itemsPerRow *= 2;
column = 0;
System.out.println();
} else {
for (int k = 0; k < nBlanks*2 - 2; k++) {
System.out.print(" ");
}
}
}
System.out.println("\n" + dots + dots);
}
//打印堆对应数组的方法
public void displayArray(int[] arr) {
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[j] + " ");
}
System.out.println();
}
}
//main函数
public static void main(String[] args) {
//一个乱序的数组
int[] arr = {10,40,20,90,50,70,30,80,60};
//创建堆排序对象，传入数组
HeapSort sort = new HeapSort(arr);
//调用堆排序方法
sort.heapSort();
}
}
最终测试结果如下图所示：
堆排序结果.png
堆排序的效率
之前已经分析过，堆排序的时间复杂度为O(NlogN)，与快速排序的时间复杂度一样，一般来说堆排序没有快速排序速度快，部分原因是堆排序在下滤操作中的循环比较复杂，而快速排序采用分治法的循环操作比较简单，但堆排序对初始数据分布不敏感，在数组基本有序的情况下，快速排序的时间复杂度会降到O(N^2)，而堆排序对于任意排列的数据，其时间复杂度都是O(NlogN)
参考文章
《Data Structures & Algorithms in Java》 Robert Lafore著
网友评论