acwing算法基础之数据结构--堆算法

1 基础知识

如何手写一个堆？

操作：

1. 插入一个数。heap[++size] = x; up(size);。
2. 求集合当中的最小值。heap[1]。
3. 删除最小值。heap[1] = heap[size]; size--; down(1);。
4. 删除任意一个元素。heap[k] = heap[size]; size--; down(k); up(k);。
5. 修改任意一个元素。heap[k] = x; down(k); up(k);

完全二叉树：对于非最后一层，都填满了；对于最后一层，左边都填满了。
小根堆：每个结点都满足，它小于左右子树结点。

2 模板

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

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

3 工程化

class Heap {
public:
    Heap (int n) {
        this->n = n;
        h.resize(n);
        ph.resize(n);
        hp.resize(n); 
    }
    
    void h_swap(int a, int b) {
        swap(ph[hp[a]], ph[hp[b]]);
        swap(hp[a], hp[b]);
        swap(h[a], h[b]);
    }

    void down(int x) {
        int t = x;
        if (2 * x <= node_last && h[2 * x] < h[t]) t = 2 * x;
        if (2 * x + 1 <= node_last && h[2 * x + 1] < h[t]) t = 2 * x + 1;
        if (t != x) {
            h_swap(t, x);
            down(t);
        }
    } 

    void up(int x) {
        while (x / 2 && h[x / 2] > h[x]) {
            h_swap(x / 2, x);
            x /= 2;
        }
    }

    void print() {
        for (int i = 1; i <= node_last; ++i) {
            cout << h[i] << ' ';
        }
        cout << endl;
        return;
    }    
    
    void insert(int x) {
        node_last++;
        insert_last++;
        h[node_last] = x;
        hp[node_last] = insert_last;
        ph[insert_last] = node_last;
        up(node_last); //在尾部插入x，故需要往上走
    }
    
    int top() {
        return h[1];
    }
    
    void pop() { //弹出堆顶元素
        h_swap(1, node_last);
        node_last--;
        down(1);        
    }
    
    void del(int k) {//删除第k个插入的结点，k从1开始计数
        k = ph[k];
        h_swap(k, node_last);
        node_last--;
        down(k);
        up(k);        
    }
    
    void update(int k, int x) {//将第k个插入的结点的值更新为x
        k = ph[k];
        h[k] = x;
        down(k);
        up(k);        
    }

private:
    int n;
    vector<int> h;
    vector<int> ph;
    vector<int> hp;
    int node_last = 0; //node_last表示最后一个结点的编号，从1开始编号
    int insert_last = 0; //insert_last表示最近的一次插入操作是第几次插入，从1开始编号
};
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