堆的实现及其应用
本篇文章记述的是堆排序，这个名字看起来好像又要介绍一个排序算法，但是排序算法是次要的，主要的是一个数据结构——堆。堆排序问题就是堆这种数据结构所衍生出来的一个应用，我们先了解一下优先队列的概念。普通的队列就是满足先进先出、后进后出的一个结构。那么优先级队列呢？出队顺序和入队顺序无关，和优先级相关，这就比如在医院看病，肯定是急诊病人优先看病。
优先级队列的应用
在操作系统中就会用到优先级队列，操作系统要同时执行多个任务，实际上操作系统是将CPU的执行周期划分为时间片，在每个时间片里只能执行一个任务，那么执行哪个任务呢？那就需要根据任务的优先级动态地选择优先级最高的任务来执行。
如何实现一个优先级队列呢？方法有很多，但是用堆来实现是最直接、最高效的。这是因为，堆和优先级队列非常相似。一个堆就可以看作一个优先级队列。很多时候，它们只是概念上的区分而已。往优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素。 优先级队列的应用场景非常多。赫夫曼编码、图的最短路径、最小生成树算法很多数据结构和算法都要依赖于优先级队列。
堆的定义及其特点
堆是一种特殊的树。我们现在就来看看，什么样的树才是堆。我罗列了两点要求，只要满足这两点，它就是一个堆。
- 堆是一个完全二叉树；
- 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
第一点，堆必须是一个完全二叉树。完全二叉树要求，除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。
第二点，堆中的每个节点的值必须大于等于（或者小于等于）其子树中每个节点的值。实际上，我们还可以换一种说法，堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。这两种表述是等价的。
对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作“大堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作“小堆”。
对于上图，1和2都是大堆；3是个小堆，而4不是堆。
完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。 如下图所示：
我们不难发现，这样的结构蕴含的规律是：左孩子在数组中的坐标是父节点的二倍，而右孩子在数组中的坐标是父节点的二倍加一。但是数组的索引却是从0开始的，堆的一个经典的实现就是数组0号位置空着，则parent (i) = i / 2(这里的除法是计算机除法，即取整)，left child (i) = 2 * i，right child (i) = 2 * i +1。
堆的具体代码实现
根据上述的堆这种数据结构的，我们可以先实现下面的基础框架代码：
1public class MaxHeap {
2 private int[] data;
3
4 //堆里有多少元素
5 private int count;
6
7 //因为0号位置不使用，所以capacity + 1
8 public MaxHeap(int capacity) {
9 data = new int[capacity + 1];
10 count = 0;
11 }
12
13 public int size(){
14 return count;
15 }
16
17 public boolean isEmpty(){
18 return count == 0;
19 }
20}
接下来需要关注的焦点是如何向上调堆，我们在向堆中添加新的元素的时候，其实是向数组的末尾添加了一个新的元素，但是往堆中插入一个元素后，我们需要继续满足堆的两个特性。如果我们把新插入的元素直接放到堆的最后，是不是不符合堆的特性了？ 于是我们就需要进行调整，让其重新满足堆的特性，这个过程叫做堆化：
堆的调整方式有两种：向上调堆和向下调堆！在这里我们可以先看看向上调堆。
向上调堆（插入元素）
其实向上调堆的过程比较简单，那就是逐步和自己的父节点进行比较，如果不满足规则就交换即可，如下图：
1public class MaxHeap {
2 protected int[] data;
3
4 //堆里有多少元素
5 protected int count;
6
7 //堆的容量
8 protected int capacity;
9
10 //因为0号位置不使用，所以capacity + 1
11 public MaxHeap(int capacity) {
12 data = new int[capacity + 1];
13 count = 0;
14 this.capacity = capacity;
15 }
16
17 //获取现存元素个数
18 public int size(){
19 return count;
20 }
21
22 //判断是否为空
23 public boolean isEmpty(){
24 return count == 0;
25 }
26
27 //插入数据
28 public void insert(int item){
29 //判断容量知否超出
30 if(count + 1 >= capacity){
31 //开始扩容
32 resize();
33 }
34
35 //先存储到末尾
36 data[count + 1] = item;
37 count++;
38
39 //开始调堆
40 shiftUp(count);
41 }
42
43 //向上调堆
44 private void shiftUp(int k) {
45 while(k > 1 && data[k / 2] < data[k]){
46 swap(k/2, k);
47 k /= 2;
48 }
49 }
50
51 //交换对应两个位置的值
52 private void swap(int i, int j){
53 int tmp = data[i];
54 data[i] = data[j];
55 data[j] = tmp;
56 }
57
58 //扩充容量
59 private void resize() {
60 int[] newData = new int[capacity * 2];
61 System.arraycopy(data, 0, newData, 0, count);
62 data = newData;
63 capacity *= 2;
64 }
65}
上面就是这个堆的实现，而且这个堆拥有扩容的功能。为了在控制台打印方便观察，实现一个打印堆的功能(数字太多控制台容易乱掉，所以限定在100个元素之内)：
1public class PrintableMaxHeap extends MaxHeap {
2 public PrintableMaxHeap(int capacity){
3 super(capacity);
4 }
5
6 // 以树状打印整个堆结构
7 public void treePrint(){
8 if( size() >= 100 ){
9 System.out.println("This print function can only work for less than 100 integer");
10 return;
11 }
12
13 System.out.println("The max heap size is: " + size());
14 System.out.println("Data in the max heap: ");
15 for( int i = 1 ; i <= size() ; i ++ ){
16 // 我们的print函数要求堆中的所有整数在[0, 100)的范围内
17 assert data[i] >= 0 && data[i] < 100;
18 System.out.print(data[i] + " ");
19 }
20 System.out.println();
21 System.out.println();
22
23 int n = size();
24 int maxLevel = 0;
25 int numberPerLevel = 1;
26 while( n > 0 ){
27 maxLevel += 1;
28 n -= numberPerLevel;
29 numberPerLevel *= 2;
30 }
31
32 int maxLevelNumber = (int)Math.pow(2, maxLevel-1);
33 int curTreeMaxLevelNumber = maxLevelNumber;
34 int index = 1;
35 for( int level = 0 ; level < maxLevel ; level ++ ){
36
37 String line1 = new String(new char[maxLevelNumber*3-1]).replace('\0', ' ');
38
39 int curLevelNumber = Math.min(count-(int)Math.pow(2,level)+1,(int)Math.pow(2,level));
40 boolean isLeft = true;
41 for( int indexCurLevel = 0 ; indexCurLevel < curLevelNumber ; index ++ , indexCurLevel ++ ){
42 line1 = putNumberInLine(data[index] , line1 , indexCurLevel , curTreeMaxLevelNumber*3-1 , isLeft );
43 isLeft = !isLeft;
44 }
45 System.out.println(line1);
46
47 if( level == maxLevel - 1 )
48 break;
49
50 String line2 = new String(new char[maxLevelNumber*3-1]).replace('\0', ' ');
51 for( int indexCurLevel = 0 ; indexCurLevel < curLevelNumber ; indexCurLevel ++ )
52 line2 = putBranchInLine( line2 , indexCurLevel , curTreeMaxLevelNumber*3-1 );
53 System.out.println(line2);
54
55 curTreeMaxLevelNumber /= 2;
56 }
57 }
58
59 private String putNumberInLine( Integer num, String line, int indexCurLevel, int curTreeWidth, boolean isLeft){
60
61 int subTreeWidth = (curTreeWidth - 1) / 2;
62 int offset = indexCurLevel * (curTreeWidth+1) + subTreeWidth;
63 assert offset + 1 < line.length();
64 if( num >= 10 )
65 line = line.substring(0, offset+0) + num.toString()
66 + line.substring(offset+2);
67 else{
68 if( isLeft)
69 line = line.substring(0, offset+0) + num.toString()
70 + line.substring(offset+1);
71 else
72 line = line.substring(0, offset+1) + num.toString()
73 + line.substring(offset+2);
74 }
75 return line;
76 }
77
78 private String putBranchInLine( String line, int indexCurLevel, int curTreeWidth){
79
80 int subTreeWidth = (curTreeWidth - 1) / 2;
81 int subSubTreeWidth = (subTreeWidth - 1) / 2;
82 int offsetLeft = indexCurLevel * (curTreeWidth+1) + subSubTreeWidth;
83 assert offsetLeft + 1 < line.length();
84 int offsetRight = indexCurLevel * (curTreeWidth+1) + subTreeWidth + 1 + subSubTreeWidth;
85 assert offsetRight < line.length();
86
87 line = line.substring(0, offsetLeft+1) + "/" + line.substring(offsetLeft+2);
88 line = line.substring(0, offsetRight) + "\\" + line.substring(offsetRight+1);
89
90 return line;
91 }
92}
接下来测试一下是否成功：
1public class MaxHeapTest {
2 public static void main(String[] args) {
3 PrintableMaxHeap maxHeap = new PrintableMaxHeap(10);
4 for (int i = 0; i < 15; i++) {
5 maxHeap.insert((int)(Math.random() * 100));
6 }
7 maxHeap.treePrint();
8 }
9}
可以看出，我们不断插入数据的时候其实就是不断调堆的过程。
向下调堆（取出元素）
取出堆顶元素，任然需要维持堆的特性，所以我们只把最后一个节点放到堆顶，然后利用同样的父子节点对比方法。对于不满足父子节点大小关系的，互换两个节点，并且重复进行这个过程，直到父子节点之间满足大小关系为止。这就是从上往下的堆化方法，也叫做向下调堆。
所以整个堆的代码如下：
1public class MaxHeap {
2 protected int[] data;
3
4 //堆里有多少元素
5 protected int count;
6
7 //堆的容量
8 protected int capacity;
9
10 //因为0号位置不使用，所以capacity + 1
11 public MaxHeap(int capacity) {
12 data = new int[capacity + 1];
13 count = 0;
14 this.capacity = capacity;
15 }
16
17 //获取现存元素个数
18 public int size(){
19 return count;
20 }
21
22 //判断是否为空
23 public boolean isEmpty(){
24 return count == 0;
25 }
26
27 //插入数据
28 public void insert(int item){
29 //判断容量知否超出
30 if(count + 1 >= capacity){
31 //开始扩容
32 resize();
33 }
34 //先存储到末尾
35 data[count + 1] = item;
36 count++;
37 //开始向上调堆
38 shiftUp(count);
39 }
40
41 //向上调堆
42 private void shiftUp(int k) {
43 while(k > 1 && data[k / 2] < data[k]){
44 swap(k/2, k);
45 k /= 2;
46 }
47 }
48
49 //取出数据
50 public int extractMax(){
51 if(count == 0) throw new RuntimeException("Heap is null");
52 int ret = data[1];
53 swap(1, count);
54 count--;
55 //开始向下调堆
56 shiftDown(1);
57 return ret;
58 }
59
60 //向下调堆
61 private void shiftDown(int k) {
62 while (2 * k <= count){
63 int j = 2 * k; //在此轮循环中，data[k]和data[j]交换位置
64 if(j + 1 <= count && data[j+1] > data[j]){
65 j++;
66 }
67 if(data[k] >= data[j]){
68 break;
69 }
70 swap(k, j);
71 k = j;
72 }
73 }
74
75 //交换对应两个位置的值
76 private void swap(int i, int j){
77 int tmp = data[i];
78 data[i] = data[j];
79 data[j] = tmp;
80 }
81
82 //扩充容量
83 private void resize() {
84 int[] newData = new int[capacity * 2];
85 System.arraycopy(data, 0, newData, 0, count);
86 data = newData;
87 capacity *= 2;
88 }
89}
一个包含n个节点的完全二叉树，树的高度不会超过logn。堆化的过程是顺着节点所在路径比较交换的，所以堆化的时间复杂度跟树的高度成正比，也就是O(logn)。插入数据和删除堆顶元素的主要逻辑就是堆化，所以往堆中插入一个元素和删除堆顶元素的时间复杂度都是O(logn)。
堆排序与heapify建堆
我们通过堆的插入操作把数组中的元素逐个插入到堆中，然后逐个取出堆顶元素防区数组中（如果是大堆从后往前放置即可）。堆排序不是稳定的排序算法，因为在排序的过程，存在将堆的最后一个节点跟堆顶节点互换的操作，所以就有可能改变值相同数据的原始相对顺序。
1public class HeapSort {
2 public static void heapSort(int[] arr){
3 MaxHeap maxHeap = new MaxHeap(arr.length);
4 for (int i = 0; i < arr.length; i++) {
5 maxHeap.insert(arr[i]);
6 }
7 for (int i = arr.length - 1; i >= 0; i--) {
8 arr[i] = maxHeap.extractMax();
9 }
10 }
11}
我们进行排序的时候，首先得把数组中的元素逐个插入到堆中，这种建堆思路的处理过程是从前往后处理数组数据，并且每个数据插入堆中时，都是从下往上堆化。但是有没有一种无需插入操作，直接把数组变成堆的方法呢？其实是有的：
因为叶子节点往下堆化只能自己跟自己比较，所以我们直接从第一个非叶子节点开始，依次堆化就行了。 非叶子节点其实很容易找出来，元素个数除以二即是第一个非叶子节点，如下图9个元素，4号即是第一个非叶子节点：
所以我们需要加入这样一个构造方法：
1
2public class MaxHeap {
3 ...
4
5 public MaxHeap(int[] arr){
6 data = new int[arr.length + 1];
7 capacity = arr.length + 1;
8 for (int i = 0; i < arr.length; i++) {
9 data[i + 1] = arr[i];
10 }
11 count = arr.length;
12 //从第一个不是叶子节点的位置开始
13 for (int i = count / 2; i >= 1; i--) {
14 shiftDown(i);
15 }
16 }
17
18 ...
19}
将n个元素逐个插入到堆中，这个操作的时间复杂度是O(nlogn)，而heapify建堆的时间复杂度为O(n)。
原地堆排序
其实堆排序完全可以变成一个原地排序算法，直接在数组上进行。因为堆的经典实现就是从1号位置开始，但是我们现在要实现的是原地排序的算法，规律完全相同，只是规律的表达式稍微有所不同。因为在上面的堆排序算法中，都需要先将数组中的元素放到堆中，然后再把堆中的元素取出来。整个程序中又额外的开辟了n个空间，事实上我们通过上面的理论方法，完全可以使一个数组在原地完成堆排序，而不需要任何的额外空间：
我们可以应用之前讲到的堆化（heapify）是我们的数组构建成一个最大堆。在这个最大堆中第一个元素就是这个数组的最大值：
最后一个非叶子节点的索引：(count - 2)/ 2、
parent(i) = (i - 1) / 2、left child (i) = 2 * i +1、right child (i) = 2 * i +2
1public class HeapSort {
2 public static void heapSort_03(int[] arr){
3 //heapify
4 for (int i = (arr.length - 1)/2; i >= 0; i--) {
5 shiftDown(arr, arr.length, i);
6 }
7 for (int i = arr.length - 1; i > 0; i--) {
8 swap(arr, 0, i);
9 shiftDown(arr, i, 0);
10 }
11 }
12
13 private static void shiftDown(int[] arr, int length, int k) {
14 while (2 * k + 1 < length){
15 int j = 2 * k + 1;
16 if(j + 1 < length && arr[j+1] > arr[j]){
17 j++;
18 }
19 if(arr[k] >= arr[j]){
20 break;
21 }
22 swap(arr, k, j);
23 k = j;
24 }
25 }
26
27 private static void swap(int[] arr, int i, int j) {
28 int tmp = arr[i];
29 arr[i] = arr[j];
30 arr[j] = tmp;
31 }
32}