数据结构与算法(12): 堆- 二叉堆

发表于   |   分类于

堆有两个性质，即结构性和堆序性。将任意节点不大于（不小于）其子节点的堆叫做最小堆（最大堆）。

  • 结构性

    堆中任意节点的值总是不大于（不小于）其子节点的值。

  • 堆序性

    堆总是一棵完全树。

二叉堆的结构是一棵完全二叉树。

1
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
    import java.util.ArrayList;
    import java.util.List;
    /**
     * 二叉堆：最小堆
     */
    public class BinaryHeap<T extends Comparable<? super T>> {
    private List<T> heap;
    public BinaryHeap() {
        this.heap = new ArrayList<>();
    }
    /**
     * 插入
     *
     * @param ele
     */
    public void insert(T ele) {
        heap.add(ele);
        percolateUp(heap.size() - 1);
    }
    /**
     * 删除最小元
     * @return
     */
    public T deleteMin() throws Exception {
        if (isEmpty()){
            throw new Exception("堆为空");
        }
        T ele = heap.get(0);
        heap.set(0, heap.get(size() - 1));
        heap.remove(size() - 1);
        if (size() > 1){
            percolateDown(0);
        }
        return ele;
    }
    /**
     * 上滤
     */
    private void percolateUp(int index) {
        int parentIndex = (index - 1) / 2;
        T tmpEle = heap.get(index);
        while (index > 0) {
            if (tmpEle.compareTo(heap.get(parentIndex)) >= 0) {
                break;
            }else {
                heap.set(index, heap.get(parentIndex));
                index = parentIndex;
                parentIndex = (index - 1)/2;
            }
        }
        heap.set(index, tmpEle);
    }
    /**
     * 下滤
     */
    private void percolateDown(int index) {
        // 先设置为左儿子索引
        int childIndex = 2 * index + 1;
        T tmpEle = heap.get(index);
        while (childIndex < size()){
            // 左右儿子大小比较, 选择较小者
            if (childIndex < size() - 1){
                int cmp = heap.get(childIndex).compareTo(heap.get(childIndex + 1));
                if (cmp > 0){
                    // 右儿子较小
                    childIndex++;
                }
            }
            int cmp = tmpEle.compareTo(heap.get(childIndex));
            if (cmp <= 0){
                break;
            }else {
                heap.set(index, heap.get(childIndex));
                index = childIndex;
                childIndex = 2 * index + 1;
            }
        }
        heap.set(index, tmpEle);
    }
    public boolean isEmpty(){
        return heap.size() == 0;
    }
    public int size(){
        return heap.size();
    }
}