二叉堆

学习数据结构与算法
2021-05-17 14:29 · 阅读时长7分钟
小课

二叉堆是一种基于二叉树的特殊存储结构,它可以看成是一棵完全二叉树。常见的有最大堆又叫大顶堆、大根堆和最小堆又叫小顶堆、小根堆。在最大堆中的任何一个子树中都有父节点的值都大于子节点的值。在最小堆中的任何一个子树中父节点的值都小于子节点。

更多介绍参考维基百科

注释

虽然二叉堆是基于二叉树的,但是实际中,我们经常使用数组来存储二叉堆,实现逻辑上的树形结构,其具备以下特点:

  • 数组中每一个元素代表二叉堆中的一个节点。
  • 父节点和子节点在数组中的存储位置存在特殊的关系,第i个节点,其左右子节点的存储位置分别是2i+1和2i+2,其父节点的存储位置是floor((i-1)/2)。

比如说使用数组存储的最大堆[100, 19, 36, 17, 3, 25, 1, 2, 7],它树形结构如下。

加载中...

通过上面可以看出,节点17的在数组中的存储位置是3,它的左右子节点存储位置分别是2*3+1=7和2*3+2=8,它的父节点的存储位置是floor((3-1)/2)=1。这个特性在后续操作、维护堆的时候非常有用。

堆的应用
  • 堆排序,利用堆数据结构实现的一种排序算法。
  • 优先队列,很多优先队列的实现都是基于堆。
  • 在图算法中的应用,比如最小生成树Prim算法,还有最短路径Dijkstra算法。

二叉堆最主要的两种操作,插入和删除,因为操作完成之后仍然要维持堆的特性,所以需要对堆中的部分节点进行调整,这两种操作的时间复杂度都是O(logN),下面以最大堆为例,看看堆的插入和删除操作。

插入逻辑

  1. 插入时先将数据插入在二叉堆最后面,也就是数组的尾部。
  2. 然后将当前节点跟它的父节点进行比较。
    *) 如果当前节点大于父节点,则将父节点与当前节点交换。
    *) 如果小于等于父节点,则停止操作。
  3. 重复第2步操作,直到当前节点小于等于父节点。

删除逻辑

  1. 首先用二叉堆最后面的节点替换最顶部的节点,即数组的最后一个元素替换第一个元素。
  2. 然后将当前节点和它的左右子节点一起对比。
    *) 如果左子节点最大,则将当前节点与左子节点交换。
    *) 如果右子节点最大,则将当前节点与右子节点交换。
    *) 如果当前节点最大,则停止操作。
  3. 重复第2步操作,直到当前节点大于等于其左右子节点。

下面看看数组[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
注意: 这个Java运行环境不支持自定义包名,并且public class name必须是Main
二叉堆优先队列