二叉堆

收录于

学习数据结构与算法

2021-05-17 14:29 · 阅读时长7分钟

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

更多介绍参考维基百科

注释

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

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

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

二叉树

123

存储的值

索引

100
0
- 19
  1
  - 17
    3
    - 2
      7
    - 7
      8
  - 3
    4
- 36
  2
  - 26
    5
  - 1
    6

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

堆的应用

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

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

插入逻辑

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

删除逻辑

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

下面看看数组[1,3,2,5,6,4]依次插入到最大堆和从最大堆删除的动画演示。

二叉堆

123

存储的值

索引

等待开始

1/24

该动画仅演示从顶部删除节点，从中间节点删除逻辑类似。

注释

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

/**
 * 自定义简单最大堆
 */
class ZXMaxHeap<T extends Comparable<T>> {

private final Object[] data;
    private int size;

public ZXMaxHeap(int capacity) {
        data = new Object[capacity];
    }

/**
     * 将当前节点跟它的父节点进行比较。
     * *) 如果当前节点大于父节点，则将父节点与当前节点交换。
     * *) 如果小于等于父节点，则停止操作。
     */
    @SuppressWarnings("unchecked")
    private void shiftUp(int index) {
        if (index == 0) {
            return;
        }
        int parent = (index - 1) / 2;
        Comparable<T> currentObject = (Comparable<T>) data[index];
        T parentObject = (T) data[parent];
        if (currentObject.compareTo(parentObject) > 0) {
            data[index] = parentObject;
            data[parent] = currentObject;
            shiftUp(parent);
        }
    }

public boolean push(T value) {
        if (isFull()) {
            return false;
        }
        data[size++] = value;
        shiftUp(size - 1);
        return true;
    }

/**
     * 将当前节点和它的左右子节点一起对比。
     * *) 如果左子节点最大，则将当前节点与左子节点交换。
     * *) 如果右子节点最大，则将当前节点与右子节点交换。
     * *) 如果当前节点最大，则停止操作。
     */
    @SuppressWarnings("unchecked")
    private void shiftDown(int index) {
        int left = (index + 1) * 2 - 1;
        if (left > size - 1) {
            return;
        }
        int right = (index + 1) * 2;
        int max = left;
        Comparable<T> leftObject = (Comparable<T>) data[left];
        T rightObject = (T) data[right];
        if (right < size && leftObject.compareTo(rightObject) < 0) {
            max = right;
        }
        Comparable<T> currentObject = (Comparable<T>) data[index];
        T maxObject = (T) data[max];
        if (currentObject.compareTo(maxObject) >= 0) {
            return;
        }
        data[index] = maxObject;
        data[max] = currentObject;
        shiftDown(max);
    }

@SuppressWarnings("unchecked")  
    public T poll() {
        if (isEmpty()) {
            return null;
        }
        Object value = data[0];
        data[0] = data[--size];
        shiftDown(0);
        return (T) value;
    }

public boolean isEmpty() {
        return size == 0;
    }

public boolean isFull() {
        return size == data.length;
    }
}

public class Main {

public static void main(String[] args) {
        int[] data = {1, 3, 2, 5, 6, 4};

ZXMaxHeap<Integer> heap = new ZXMaxHeap<>(6);
        assert heap.isEmpty();
        for (int datum : data) {
            heap.push(datum);
        }
        assert heap.isFull();
        while (!heap.isEmpty()) {
            System.out.println(heap.poll());
        }
        assert heap.isEmpty();
    }
}

注意: 这个Java运行环境不支持自定义包名，并且public class name必须是Main

二叉堆优先队列

二叉堆

学习数据结构与算法

堆的应用

二叉树

冒泡排序