二叉堆是一种基于二叉树的特殊存储结构,它可以看成是一棵完全二叉树。常见的有最大堆又叫大顶堆、大根堆和最小堆又叫小顶堆、小根堆。在最大堆中的任何一个子树中都有父节点的值都大于子节点的值。在最小堆中的任何一个子树中父节点的值都小于子节点。
更多介绍参考维基百科
注释虽然二叉堆是基于二叉树的,但是实际中,我们经常使用数组来存储二叉堆,实现逻辑上的树形结构,其具备以下特点:
比如说使用数组存储的最大堆[100, 19, 36, 17, 3, 25, 1, 2, 7]
,它树形结构如下。
存储的值
索引
通过上面可以看出,节点17的在数组中的存储位置是3,它的左右子节点存储位置分别是2*3+1=7和2*3+2=8,它的父节点的存储位置是floor((3-1)/2)=1。这个特性在后续操作、维护堆的时候非常有用。
二叉堆最主要的两种操作,插入和删除,因为操作完成之后仍然要维持堆的特性,所以需要对堆中的部分节点进行调整,这两种操作的时间复杂度都是O(logN),下面以最大堆为例,看看堆的插入和删除操作。
插入逻辑
删除逻辑
下面看看数组[1,3,2,5,6,4]依次插入到最大堆和从最大堆删除的动画演示。
存储的值
索引
该动画仅演示从顶部删除节点,从中间节点删除逻辑类似。
注释1/**
2 * 自定义简单最大堆
3 */
4class ZXMaxHeap<T extends Comparable<T>> {
5
6 private final Object[] data;
7 private int size;
8
9 public ZXMaxHeap(int capacity) {
10 data = new Object[capacity];
11 }
12
13 /**
14 * 将当前节点跟它的父节点进行比较。
15 * *) 如果当前节点大于父节点,则将父节点与当前节点交换。
16 * *) 如果小于等于父节点,则停止操作。
17 */
18 @SuppressWarnings("unchecked")
19 private void shiftUp(int index) {
20 if (index == 0) {
21 return;
22 }
23 int parent = (index - 1) / 2;
24 Comparable<T> currentObject = (Comparable<T>) data[index];
25 T parentObject = (T) data[parent];
26 if (currentObject.compareTo(parentObject) > 0) {
27 data[index] = parentObject;
28 data[parent] = currentObject;
29 shiftUp(parent);
30 }
31 }
32
33 public boolean push(T value) {
34 if (isFull()) {
35 return false;
36 }
37 data[size++] = value;
38 shiftUp(size - 1);
39 return true;
40 }
41
42 /**
43 * 将当前节点和它的左右子节点一起对比。
44 * *) 如果左子节点最大,则将当前节点与左子节点交换。
45 * *) 如果右子节点最大,则将当前节点与右子节点交换。
46 * *) 如果当前节点最大,则停止操作。
47 */
48 @SuppressWarnings("unchecked")
49 private void shiftDown(int index) {
50 int left = (index + 1) * 2 - 1;
51 if (left > size - 1) {
52 return;
53 }
54 int right = (index + 1) * 2;
55 int max = left;
56 Comparable<T> leftObject = (Comparable<T>) data[left];
57 T rightObject = (T) data[right];
58 if (right < size && leftObject.compareTo(rightObject) < 0) {
59 max = right;
60 }
61 Comparable<T> currentObject = (Comparable<T>) data[index];
62 T maxObject = (T) data[max];
63 if (currentObject.compareTo(maxObject) >= 0) {
64 return;
65 }
66 data[index] = maxObject;
67 data[max] = currentObject;
68 shiftDown(max);
69 }
70
71 @SuppressWarnings("unchecked")
72 public T poll() {
73 if (isEmpty()) {
74 return null;
75 }
76 Object value = data[0];
77 data[0] = data[--size];
78 shiftDown(0);
79 return (T) value;
80 }
81
82 public boolean isEmpty() {
83 return size == 0;
84 }
85
86 public boolean isFull() {
87 return size == data.length;
88 }
89}
90
91public class Main {
92
93 public static void main(String[] args) {
94 int[] data = {1, 3, 2, 5, 6, 4};
95
96 ZXMaxHeap<Integer> heap = new ZXMaxHeap<>(6);
97 assert heap.isEmpty();
98 for (int datum : data) {
99 heap.push(datum);
100 }
101 assert heap.isFull();
102 while (!heap.isEmpty()) {
103 System.out.println(heap.poll());
104 }
105 assert heap.isEmpty();
106 }
107}
108