[模板] 二叉堆 - 优先队列的二叉堆数组实现_数组模拟 二叉堆

  最近开始学数据结构，一直无心更新博客，今天结束集训，晚上打算码一下最近的进度。

/*
 * 创建一个最大容量为MaxSize的int型堆：MaxHeap<int> que(MaxSize);
 * 默认最大容量为1007：MaxHeap<int> que;
 *
 * 作为优先队列：
 *      pop();        同优先队列pop()，如果队列已为空还要执行pop，就会执行死循环以报错。
 *      push();       同优先队列push()，如果队列已满，就会执行死循环以报错。
 *      top();        同优先队列top()
 *      empty();      同优先队列empty()
 *
 * 支持结构体，需要重载小于号(<)。
 * 其它自带类型数据可以调用functional里的库函数：
 *      #include <functional>
 *      MaxHeap<int, greater<int> > que; //最小化堆
 *      MaxHeap<int> q; 等价于 MaxHeap<int, less<int> > q; //最大化堆
 */

template<class T, class Compare = std::less<T> >
class MaxHeap {
private:
    T *Heap;// 数据
    int Capacity, Size;// 总的容量，实际容量
    Compare cmp;
    void filterdown(int start, int end) {// 最大堆的向下调整算法
        int index = start;
        int cur = index << 1;// 先指向左儿子
        T tmp = Heap[index];
        while (cur <= end) {
            if (cur < end && cmp(Heap[cur], Heap[cur + 1])) {// cur+1是右儿子
                cur++;// 如果右儿子比较大，就将cur指向右儿子
            }
            if (!cmp(tmp, Heap[cur])) break;//调整结束
            Heap[index] = Heap[cur];
            index = cur;
            cur <<= 1;
        }
        Heap[index] = tmp;
    }

    void filterup(int start) {// 最大堆的向上调整算法(从start开始向上直到1，调整堆)
        int cur = start;
        int pre = cur >> 1;
        T tmp = Heap[cur];
        while (cur > 1) {
            if (!cmp(Heap[pre], tmp)) break;
            Heap[cur] = Heap[pre];
            cur = pre;
            pre >>= 1;
        }
        Heap[cur] = tmp;
    }

    int getindex(T data) {// 返回data在二叉堆中的索引
        for (int i = 1; i <= Size; i++) if (Heap[i] == data) return i;
        return -1;
    }

    bool remove(T data) {// 删除最大堆中的data，成功返回true
        if (Size == 0) return false;
        int index = getindex(data);// 获取data在二叉堆中的索引
        if (index == -1) return false;
        Heap[index] = Heap[Size--];
        filterdown(index, Size);
        return true;
    }

    void print() {// 打印二叉堆
        for (int i = 1; i < Size; i++) cout << Heap[i] << ' ';
        cout << Heap[Size] << endl;
    }

public:
    MaxHeap(T *tmp, int len, int capactity) {//要传入的数组和长度，以及堆的最大size，数组下标从1开始
        Capacity = capactity;
        Size = 0;
        Heap = new T[capactity + 7];
        if (len == 0) return;
        for (int i = 1; i <= len; i++) push(tmp[i]);
    }

    MaxHeap(int capactity = 1007) {
        Capacity = capactity;
        Size = 0;
        Heap = new T[capactity + 7];
    }

    ~MaxHeap() {
        delete (Heap);
    }

    void pop() {
        if (Size == 0) return;
        Heap[1] = Heap[Size--];
        filterdown(1, Size);
    }

    T top() {
        if (Size == 0) while (true);
        return Heap[1];
    }

    bool empty() {
        return Size == 0;
    }

    bool push(T data) {// 将data插入到二叉堆中
        if (Size == Capacity) return false;
        Heap[++Size] = data;
        filterup(Size);
        return true;
    }
};
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113