图解二叉堆
二叉堆本质上其实就是一种完全二叉树(不熟悉二叉树的可以看前面的文章：图解二叉树，它分为两种类型：
-
最大堆：堆中任何一个父节点的值都大于等于它左右子节点的值
-
最小堆：显然和最大堆相反，堆中任何一个父节点的值都小于等于它左右子节点的值
对于一个二叉堆的操作主要包含了两个：插入节点和删除节点；接下来会对这两种操作进行具体的说明，说明的对象都是最小堆，如果理解了最小堆的操作，那么最大堆的操作就易如反掌了。
插入节点 (最小堆)
插入一个节点主要的逻辑就是在二叉树的最后节点上安置新的节点，然后比较此节点和父节点的大小。如果是小于父节点，那么就不用操作，直接生成此二叉堆；如果是大于父节点，那么将此节点和父节点位置互换(也就是上浮操作)，将互换后的父节点作为新的节点，再进行新节点和父节点的大小比较，直到新节点小于父节点或者新节点为根节点，结束。文字的表现力依旧比较复杂，下面就看插入的流程图吧，结合流程图会更加贴切的理解插入过程。
-
在现有的二叉堆 ( 0, 3, 2, 7, 9, 5, 6, 10, 8 ) 中插入新的节点 1
-
新节点与父节点对比，新节点 1 小于 父节点 9，那么就互换位置
-
互换后的节点 1 再与其父节点对比，1 小于其父节点 3，再次互换位置
-
再看此时的新节点 1，对于其现有父节点 0，它是大于其父节点的，所以终止上浮操作，生成最终的二叉堆 ( 0 1 2 7 3 5 6 10 8 9 )，如上图所示。
下面看具体的代码实现：
1 /**
2 * 添加一个结点
3 *
4 * @param element 结点值
5 */
6 public void addNode(Integer element) {
7 _data.add(element);
8 up();
9 }
10
11 /**
12 * 进行上浮操作
13 */
14 private void up() {
15 int tempIndex = _data.size() - 1;
16 int parentIndex = (tempIndex - 1) / 2;
17 Integer temp = _data.get(tempIndex);
18
19 while (tempIndex > 0) {
20 int cmp = _data.get(parentIndex) - temp;
21 if (cmp <= 0) {
22 break;
23 } else {
24 _data.set(tempIndex, _data.get(parentIndex));
25 tempIndex = parentIndex;
26 parentIndex = (parentIndex - 1) / 2;
27 }
28 }
29 _data.set(tempIndex, temp);
30 }
删除节点 (最小堆)
删除节点的操作和逻辑要比添加节点稍微复杂那么一丢丢，但是其本质还是一样的，比较子节点和父节点的大小进行下沉操作。删除某个节点，先将此节点移除，然后将最后一个节点暂时安放在删除节点的位置；开始比较最后一个节点和其左右子节点的大小，如果是比两个子节点都小，那么终止下沉操作，生成新的二叉堆，如果是比其中任何一个子节点大，那么就将此节点和其子节点中最小的那个互换位置，依次循环，直到没有子节点或者比子节点小，终止下沉操作，生成最终的新二叉堆。下面请看图解：
-
在原二叉堆 ( 0 1 2 7 3 5 6 10 8 9 ) 中删除其根节点 0，第一步就是将最后节点 9 暂时移到根节点处
-
第二步对比 9 这个节点和其子节点中最小的大小，最小节点为 1，而且 9 比其子节点 1 要大，那么就将其互换位置，得到如下图所示：
-
第三步继续对比此时的 9 节点和其子节点的大小，此时它的子节点中最小的是 3 ，而 9 节点又比 3 要大，那么继续互换位置，如下图：
-
第四步准备继续对比，发现此时的 9 节点没有子节点了，那么就终止对比，生成新的二叉堆 ( 1 3 2 7 9 5 6 10 8 )：
代码实现起来如下：
1/**
2 * 删除一个结点，同时进行下沉操作
3 *
4 * @param element 删除的结点
5 */
6 public void deleteNode(Integer element) {
7 if (_data.isEmpty()) {
8 return;
9 }
10 int index = _data.indexOf(element);
11 if (index == -1) {
12 return;
13 }
14 if (index == _data.size() - 1) {
15 _data.remove(_data.size() - 1);
16 return;
17 }
18 int size = _data.size();
19 _data.set(index, _data.get(size - 1));
20 _data.remove(size - 1);
21 if (size > 1) {
22 down(index, _data.size() - 1);
23 }
24 }
25
26 /**
27 * 下沉
28 *
29 * @param start 下沉起始坐标
30 * @param end 下沉终点坐标
31 */
32 private void down(int start, int end) {
33 int left = start * 2 + 1;
34 Integer temp = _data.get(start);
35 while (left <= end) {
36 boolean max = true;
37 // 防止index越界
38 if (left + 1 <= end) {
39 // 对比左右子节点，如果右子节点比左小，那么left取右子节点的下标
40 max = (_data.get(left) - _data.get(left + 1)) < 0;
41 }
42 if (!max && left <= end) {
43 left++;
44 }
45 // 如果子节点小于父节点，那么交换位置
46 // 并且继续检查子节点和其子节点的大小关系
47 max = (temp - _data.get(left)) > 0;
48 if (!max) break;
49 else {
50 _data.set(start, _data.get(left));
51 start = left;
52 left = left * 2 + 1;
53 }
54 }
55 _data.set(start, temp);
56 }
二叉堆在理解二叉树的知识之后，上手理解还是比较轻松的，而且二叉堆的应用很广，比如我们使用的堆排序，就是完美的使用了二叉堆中删除节点的操作，可以试想一下，对于一个最小堆来说，依次删除根节点，拿到顺序不就是从最小值开始的么。而且我们还可以取一个数组或者列表中前K个最小值。所以二叉堆的知识还是有必要熟练掌握的！
下面我把整体代码贴出来，以便大家在熟悉过程中可以跟着代码结果来对比。
1import java.util.ArrayList;
2import java.util.List;
3
4class BinaryHeap {
5
6 private List<Integer> _data;
7
8 public BinaryHeap() {
9 _data = new ArrayList<>();
10 }
11
12 /**
13 * 添加一个结点
14 *
15 * @param element 结点值
16 */
17 public void addNode(Integer element) {
18 _data.add(element);
19 up();
20 }
21
22 /**
23 * 进行上浮操作
24 */
25 private void up() {
26 int tempIndex = _data.size() - 1;
27 int parentIndex = (tempIndex - 1) / 2;
28 Integer temp = _data.get(tempIndex);
29
30 while (tempIndex > 0) {
31 int cmp = _data.get(parentIndex) - temp;
32 if (cmp <= 0) {
33 break;
34 } else {
35 _data.set(tempIndex, _data.get(parentIndex));
36 tempIndex = parentIndex;
37 parentIndex = (parentIndex - 1) / 2;
38 }
39 }
40 _data.set(tempIndex, temp);
41 }
42
43 /**
44 * 删除一个结点，同时进行下沉操作
45 *
46 * @param element 删除的结点
47 */
48 public void deleteNode(Integer element) {
49 if (_data.isEmpty()) {
50 return;
51 }
52 int index = _data.indexOf(element);
53 if (index == -1) {
54 return;
55 }
56 if (index == _data.size() - 1) {
57 _data.remove(_data.size() - 1);
58 return;
59 }
60 int size = _data.size();
61 _data.set(index, _data.get(size - 1));
62 _data.remove(size - 1);
63 if (size > 1) {
64 down(index, _data.size() - 1);
65 }
66 }
67
68 /**
69 * 下沉
70 *
71 * @param start 下沉起始坐标
72 * @param end 下沉终点坐标
73 */
74 private void down(int start, int end) {
75 int left = start * 2 + 1;
76 Integer temp = _data.get(start);
77 while (left <= end) {
78 boolean max = true;
79 // 防止index越界
80 if (left + 1 <= end) {
81 // 对比左右子节点，如果右子节点比左小，那么left取右子节点的下标
82 max = (_data.get(left) - _data.get(left + 1)) < 0;
83 }
84 if (!max && left <= end) {
85 left++;
86 }
87 // 如果子节点小于父节点，那么交换位置
88 // 并且继续检查子节点和其子节点的大小关系
89 max = (temp - _data.get(left)) > 0;
90 if (!max) break;
91 else {
92 _data.set(start, _data.get(left));
93 start = left;
94 left = left * 2 + 1;
95 }
96 }
97 _data.set(start, temp);
98 }
99
100 @Override
101 public String toString() {
102 StringBuilder result = new StringBuilder();
103 _data.forEach(element -> result.append(element).append(" "));
104 return result.toString();
105 }
106
107 public static void main(String[] args) {
108 Integer[] data = {0, 3, 2, 7, 9, 5, 6, 10, 8};
109 BinaryHeap binaryHeap = new BinaryHeap();
110 for (Integer element : data) {
111 binaryHeap.addNode(element);
112 }
113 binaryHeap.addNode(1);
114 System.out.println(binaryHeap.toString());
115 binaryHeap.deleteNode(0);
116 System.out.println(binaryHeap.toString());
117 }
118}
如果本文章你发现有不正确或者不足之处，欢迎你在下方留言或者扫描下方的二维码留言也可！
原文始发于微信公众号（Taonce）：图解二叉堆
