释放双眼，带上耳机，听听看~！
目录
一、基本原理
二、代码实现
1、二叉堆
2、堆排序
3、优先队列
一、基本原理
堆排序基于二叉堆（大顶堆、小顶堆）这一数据结构，二叉堆形状上就是完全二叉树。大顶堆就是任何一个节点都大于等于它的左孩子、右孩子；小顶堆则是任何一个节点都小于等于它的左孩子、右孩子。这两种结构的特点在于最大值、最小值放在堆顶的位置，另外父节点大于或小于其左右孩子节点。堆排序就是将数组转换为最大堆的形式，然后不断删除堆顶元素将其放在最后面的位置，同时重新维护成最大堆，当堆中元素为空时排序也就完成。
堆排序有些类似于选择排序，它每一轮将最大值上浮到数组最左端，然后将其交换到数组未排序的右端。与快速排序相比，两者平均时间复杂度均为O(nlogn)，都是不稳定排序。不过，快排的最差时间复杂度为O(n^2)而堆排序最差也稳定在O(nlogn)，在空间方面，快排的递归和非递归都是O(n)而堆排序是O(1)。与归并排序相比，两者时间复杂度的上界均为O(nlogn)，两者的区别在于，归并排序的常数小于堆排序，堆排序使用的空间小于归并排序（O(n)）。堆排序很少使用，一般仅在可用空间较少（无法使用归并排序）的实时（或快排无法适应时间限制）嵌入式系统中使用。
在O(nlogn)级别的排序算法中，堆排序不像快速排序、归并排序在实践中经常使用到，但是堆这种结构在很多地方经常用到。堆有如下应用场景：1）优先队列：使用二叉堆而不是二叉树实现优先队列（图算法如普里姆算法、地杰斯特拉算法会用到优先队列），因为二叉堆可以提供O(logn)时间复杂度的insert()，delete()，extractMax()，decreaseKey()等操作。二叉堆的变种二项堆和斐波那契堆（Binomoial Heap and Fibonacci Heap）可以提供O(logn)级别的union操作，这在二叉堆中需要O(n)的时间。2）统计：堆结构可以高效求解数组中第k小/大元素等问题。
二、代码实现
1、二叉堆
二叉堆是实现优先级队列、堆排序的基础。二叉堆的主要操作有二叉堆的构建、删除、插入，基本操作有最后一个元素的上浮调整和任一元素的下沉调整，其中，二叉堆的构建本质上就是所有非叶子节点的下沉调整；删除操作则是用最后一个元素替换堆顶元素，然后对堆顶元素进行下沉调整；插入操作则是在堆后面插入一个元素，然后对堆中最后一个元素进行上浮调整。此外，二叉堆也可以实现减小或增大节点的值、合并两个堆等操作。合并两个堆的最优方法是将两个二叉堆（元素个数分别为n、k）首尾相连放在一个数组中，然后构建新的二叉堆，时间复杂度为O(logn*logk)。如果经常需要合并两个堆的操作，那么使用二项式堆更好，其时间复杂度为O(logn)。
这里的二叉堆采用数组作为物理存储结构，因为当父节点的下标为 i 时，其左孩子的下标为2*i + 1，右孩子的下标为2*i + 2（如果存在的话，i = 0, 1, 2, …），父节点为(i – 1) / 2，可以随机访问。另外，从左到右遍历数组相当于对二叉堆进行层序遍历。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
2 private int[] data;
3 private int size; //堆的实际大小
4 private int maxSize; //堆的最大大小
5
6 public MaxHeap(int capacity) {
7 data = new int[capacity + 1];
8 maxSize = capacity;
9 size = 0;
10 data[0] = Integer.MAX_VALUE;
11 }
12
13 //返回节点i的父节点的下标
14 private int parent(int i) {
15 return i / 2;
16 }
17 //返回节点i的左孩子节点的下标
18 private int leftChild(int i) {
19 return 2 * i;
20 }
21 //返回节点i的右孩子节点的下标
22 private int rightChild(int i) {
23 return 2 * i + 1;
24 }
25
26 //判断给定节点是否是叶子节点
27 private boolean isLeaf(int i) {
28 if (i > (size / 2) && i <= size) {
29 return true;
30 }
31 return false;
32 }
33 //交换两个位置的元素
34 private void swap(int i, int j) {
35 int temp = data[i];
36 data[i] = data[j];
37 data[j] = temp;
38 }
39 //打印堆中所有元素
40 public void print() {
41 int num = 1;
42 int start = 1;
43 int step = 1;
44 for (int i=1; i<=size; i++) {
45 System.out.print(data[i] +" ");
46 if (i - start + 1 == step) {
47 step = step * 2;
48 start = i + 1;
49 System.out.println();
50 }
51 }
52 }
53
54 //对堆中最后一个元素进行上浮调整
55 public void upAdjust() {
56 int i = size;
57 while (i/2 > 0 && data[i] > data[i/2]) {
58 swap(i, i/2);
59 i = i / 2;
60 }
61 }
62 //对堆中pos处的元素进行下沉调整（堆化子树）
63 public void downAdjust(int pos) {
64 int temp = data[pos];
65
66 int parentIndex = pos;
67 int childIndex = leftChild(parentIndex);
68 while (childIndex < size) {
69 //拿到cur节点较大的孩子节点
70 if (childIndex+1<size && data[childIndex+1]>data[childIndex]){
71 childIndex = childIndex + 1;
72 }
73 //如果父节点均大于等于两个孩子节点，直接跳出
74 if (temp >= data[childIndex]) {
75 break;
76 }
77 //交换父子节点（直接赋值即可，无需交换）
78 data[parentIndex] = data[childIndex];
79 parentIndex = childIndex;
80 childIndex = leftChild(childIndex);
81 }
82 data[parentIndex] = temp;
83 }
84 //下沉调整的另一种写法
85 private void heapify(int i) {
86 while (true) {
87 int maxPos = i;
88 if (i+2 <= size && data[i]<data[i*2]) {
89 maxPos = i*2;
90 }
91 if (i*2+1 <= size && data[maxPos]<data[i*2+1]) {
92 maxPos = i*2 + 1;
93 }
94
95 if (maxPos == i) {
96 break;
97 }
98 swap(i, maxPos);
99 i = maxPos;
100 }
101 }
102 //下沉调整的递归写法
103 private void maxHeapify(int pos) {
104 if (isLeaf(pos)) {
105 return;
106 }
107
108 if ((leftChild(pos)<=size && data[pos]<data[leftChild(pos)]) ||
109 (rightChild(pos)<=size && data[pos]<data[rightChild(pos)])) {
110 if (data[leftChild(pos)] > data[rightChild(pos)]) {
111 swap(pos, leftChild(pos));
112 maxHeapify(leftChild(pos));
113 } else {
114 swap(pos, rightChild(pos));
115 maxHeapify(rightChild(pos));
116 }
117 }
118 }
119
120 //插入元素
121 public void insert(int e) {
122 if (size >= maxSize) {
123 return; //堆满了
124 }
125
126 ++size;
127 data[size] = e;
128 upAdjust();
129 }
130 //删除最大元素
131 public int extractMax() throws Exception {
132 if (size == 0) {
133 throw new Exception("Heap is empty");
134 }
135
136 int temp = data[1];
137
138 data[1] = data[size--];
139 maxHeapify(1);
140
141 return temp;
142 }
143 //查询最大元素
144 public int getMax() {
145 if (size == 0) {
146 return Integer.MIN_VALUE;
147 }
148 return data[1];
149 }
150
151}
152
利用优先队列创建大顶堆，由于PriorityQueue默认是小顶堆，这里需要使用Collections.reverseOrder()方法。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
2
3 public static void main(String[] args) {
4
5 //使用优先队列得到大顶堆
6 PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
7 heap.add(10);
8 heap.add(30);
9 heap.add(20);
10 heap.add(400);
11 heap.add(400);
12
13 //删除堆顶元素、查看堆顶元素
14 System.out.println(heap.poll() +" "+ heap.peek());
15 //遍历堆中元素
16 Iterator<Integer> itr = heap.iterator();
17 while (itr.hasNext()) {
18 System.out.print(itr.next()+" ");
19 }
20 System.out.println();
21 //获得元素数组
22 Object[] arr = heap.toArray();
23 for (int i=0; i<arr.length; i++) {
24 //System.out.print(arr[i].toString()+" ");
25 System.out.print(arr[i]+" ");
26 }
27 System.out.println();
28
29 }
30
31}
32
运行结果为：
2、堆排序
堆排序的基础是二叉堆的节点下沉调整操作。要实现堆排序，第一步需要将无序数组构建为大顶堆，第二步循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶。具体流程如下：
1）由输入数据构建一个大顶堆，此时最大元素被放在堆顶；
2）将堆顶元素与最后一个元素交换，并将堆的大小减1，确定堆中最大元素的最终位置（类似于选择排序）；
3）对交换后的堆顶元素进行下沉调整，重复以上步骤直到堆中元素只有一个或为空。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
2
3 //堆排序
4 public static void heapSort(int[] arr) {
5 //buildHeap(arr, arr.length-1);
6 buildHeap(arr);
7 int k = arr.length - 1;
8 //while (k >= 0) {
9 while (k > 0) {
10 swap(arr, 0, k);
11 --k;
12 //heapify(arr, k, 0);
13 downAdjust(arr, k, 0);
14 }
15 }
16
17 //堆的构建
18 //将整个数组调整为大顶堆（本质上就是让所有非叶子节点下沉）
19 private static void buildHeap(int[] arr) {
20 if (arr == null) {
21 return;
22 }
23 //从最后一个非叶子节点开始，依次进行下沉调整
24 for (int i=(arr.length-2)/2; i>=0; i--) {
25 //heapify(arr, arr.length-1, i);
26 downAdjust(arr,arr.length-1, i);
27 }
28 System.out.println(Arrays.toString(arr));
29 }
30 //将数组arr[0 ... n]构建为大顶堆
31 private static void buildHeap(int[] arr, int n) {
32 if (arr == null) {
33 return;
34 }
35 for (int i=n/2; i>=0; i--) {
36 //heapify(arr, n, i);
37 downAdjust(arr, n, i);
38 }
39 System.out.println(Arrays.toString(arr));
40 }
41
42 //对数组最后一个元素进行上浮调整，堆的范围为[0 ... arr.length-1]
43 private static void upAdjust(int[] arr) {
44 int childIndex = arr.length - 1;
45 int parentIndex = (childIndex - 1) / 2;
46
47 int temp = arr[childIndex];
48 while (childIndex>0 && temp<arr[parentIndex]) {
49 arr[childIndex] = arr[parentIndex];
50 childIndex = parentIndex;
51 parentIndex = (parentIndex - 1) / 2;
52 }
53 }
54 //对数组下标为pos的元素进行下沉调整，堆的范围为[0 ... n]
55 private static void downAdjust(int[] arr, int n, int pos) {
56 int temp = arr[pos];
57
58 int parentIndex = pos;
59 int childIndex = 2 * pos + 1;
60 while (childIndex <= n) {
61 //拿到cur值较大的孩子节点
62 if (childIndex+1<=n && arr[childIndex+1]>arr[childIndex]){
63 childIndex = childIndex + 1;
64 }
65 //如果父节点均大于等于两个孩子节点，直接跳出
66 if (temp >= arr[childIndex]) {
67 break;
68 }
69 //交换父子节点（直接赋值即可，无需交换）
70 arr[parentIndex] = arr[childIndex];
71 parentIndex = childIndex;
72 childIndex = 2 * childIndex + 1;
73 }
74 arr[parentIndex] = temp;
75 }
76 //对数组下标为pos的元素进行下沉调整，堆的范围为[0 ... n]
77 private static void heapify(int[] arr, int n, int i) {
78 while (true) {
79 int maxPos = i;
80 if (2*i+1<=n && arr[i]<arr[i*2+1]) {
81 maxPos = 2*i + 1;
82 }
83 if (2*i+2<=n && arr[maxPos]<arr[i*2+2]) {
84 maxPos = 2*i + 2;
85 }
86
87 if (maxPos == i) {
88 break;
89 }
90 swap(arr, i, maxPos);
91 i = maxPos;
92 }
93 }
94
95}
96
97
3、优先队列
我们知道队列就是先进先出的集合，而优先队列则是按照优先级出队，分为最大优先队列（不管入队顺序，当前队列中最大元素出队，可以用大顶堆实现）和最小优先队列（不管入队顺序，当前队列中最小元素出队，可以用小顶堆实现）。每一次入队操作就是在二叉堆尾部插入元素并对其进行上浮调整，每一次出队操作就是将二叉堆堆顶元素删除，并对新的堆顶元素进行下沉调整，因此优先队列的入队操作、出队操作的时间复杂度均为O(logn)。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
2 private int[] data;
3 private int size;
4
5 public MyPriorityQueue() {
6 //队列初始长度
7 data = new int[8];
8 }
9
10 //上浮调整
11 private void upAdjust() {
12 int childIndex = size - 1; //最后一个元素
13 int parentIndex = childIndex / 2; //最后一个元素的父节点
14
15 int temp = data[childIndex]; //暂存需要调整的最后一个元素
16 while (childIndex > 0 && temp > data[parentIndex]) {
17 data[childIndex] = data[parentIndex];
18 childIndex = parentIndex;
19 parentIndex = parentIndex / 2;
20 }
21 data[childIndex] = temp;
22 }
23 //下沉调整
24 private void downAdjust() {
25 int parentIndex = 0;
26 int childIndex = 1;
27
28 int temp = data[parentIndex]; //暂存需要调整的堆顶元素
29 while (childIndex < size) {
30 //如果有右孩子，则定位到较大的孩子节点
31 if (childIndex+1<size && data[childIndex+1]>data[childIndex]) {
32 childIndex = childIndex + 1;
33 }
34 //如果父节点均大于等于两个孩子节点，则直接跳出
35 if (temp >= data[childIndex]) {
36 break;
37 }
38 //交换父子节点
39 data[parentIndex] = data[childIndex];
40 parentIndex = childIndex;
41 childIndex = 2 * childIndex + 1;
42 }
43 data[parentIndex] = temp;
44 }
45 //扩容
46 private void resize() {
47 //将队列容量翻倍
48 int newSize = this.size * 2;
49 this.data = Arrays.copyOf(this.data, newSize);
50 }
51
52 //入队
53 public void enqueue(int e) {
54 //如果队列已满，则扩容
55 if (size >= data.length) {
56 resize();
57 }
58 data[size++] = e;
59 upAdjust();
60 }
61 //出队
62 public int dequeue() throws Exception {
63 if (size <= 0) {
64 throw new Exception("queue is empty");
65 }
66
67 int head = data[0]; //暂存堆顶元素
68
69 data[0] = data[--size]; //移动最后一个元素到堆顶
70 downAdjust();
71
72 return head;
73 }
74 //判空
75 public boolean isEmpty() {
76 return size == 0;
77 }
78 //查询队列容量
79 public int getCapacity() {
80 return data.length;
81 }
82 //查询队列元素个数
83 public int size() {
84 return size;
85 }
86 //查询堆顶元素
87 public int getHead() {
88 return data[0];
89 }
90}
91
泛型实现：
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
2 private Key[] data;
3 private int size = 0;
4
5 public MaxPQ(int capacity) {
6 data = (Key[])new Comparable[capacity + 1];
7 }
8
9 //返回当前队列中最大元素
10 public Key getMax() {
11 return data[1];
12 }
13 //删除最大元素（出队）
14 public Key delMax() {
15 Key max = data[1]; //暂存
16
17 swap(1, size);
18 data[size] = null;
19 size--;
20 sink(1);
21
22 return max;
23 }
24 //插入元素（入队）
25 public void insert(Key e) {
26 size++;
27 data[size] = e;
28 swim(size);
29 }
30
31 //将第k个元素进行上浮调整
32 private void swim(int k) {
33 //如果上浮到堆顶就停止上浮
34 while (k>1 && less(parent(k), k)) {
35 //如果第k个元素比上层大，将它们交换
36 swap(parent(k), k);
37 k = parent(k);
38 }
39 }
40 //将第k个元素进行下沉调整
41 private void sink(int k) {
42 //如果沉到堆底就停止下沉
43 while (leftChild(k) <= size) {
44 int larger = leftChild(k);
45 if (rightChild(k)<=size && less(larger, rightChild(k))) {
46 larger = rightChild(k);
47 }
48 //如果节点k比两个孩子都大，就不用下沉
49 if (less(larger, k)) {
50 break;
51 }
52 //交换k和其较大的孩子节点
53 swap(k, larger);
54 k = larger;
55 }
56 }
57
58 //父节点
59 private int parent(int i) {
60 return i / 2;
61 }
62 //左孩子节点
63 private int leftChild(int i) {
64 return i * 2;
65 }
66 //右孩子节点
67 private int rightChild(int i) {
68 return i * 2 + 1;
69 }
70 //判断data[i]是否比data[j]小
71 private boolean less(int i, int j) {
72 return data[i].compareTo(data[j]) < 0;
73 }
74 //交换两个元素
75 private void swap(int i, int j) {
76 Key temp = data[i];
77 data[i] = data[j];
78 data[j] = temp;
79 }
80}
81
