手写二叉堆

发表于 更新于 分类于 Artalk： loading...

本文主要包括堆的原理介绍和代码实现

具体的数据结构：数组、链表

抽象的数据结构：二叉树、队列、栈、优先队列、堆等

堆：是一种抽象的数据结构，我们在插入或删除元素后堆将自动调整结构以维持有序，可用二叉树实现。

优先队列：是一种抽象的数据结构，在队列的基础上定义了元素的优先级，可用堆实现。

堆排序：使用数据结构堆实现的排序算法。

因此，优先队列与堆排序

相同点：都使用了堆。

不同点：优先队列是数据结构，堆排序是排序算法。

简概

数据结构-堆

首先，堆是一个完全二叉树。知识点备忘

本次讨论的默认是小根堆。（即每一个根结点的值小于等于其左右孩子节点的值）

如何存储堆

image-20211103155749977

使用一维数组来存储，一个节点编号为 xx ，其左孩子编号为 2x2x ，右孩子编号为 2x+12x+1

为了编程方便，用数组存储时，下标也从11开始

最主要的两个操作

向下调整，将一个节点向下移动，down()down()，

  • 一个节点的值变大了，向下移动

向上调整，将一个节点向上移动，up()up()，

  • 一个节点的值变小了，向上移动，不断与父节点比较，交换。

堆的五种基本操作

插入操作

heap[++ size] = x; up(size);

在整个堆的最后一个位置插入x，然后不断向上移动。

求最小值

return heap[1];

删除最小值

将堆的最后一个元素覆盖到heap[1]，size–，然后向下调整

heap[1] = heap[size]; size --; down(1);

删除任意一个元素

先将堆的最后一个元素覆盖到要删除的元素，如果变大了，就向下调整；变小了，就向上调整。

这里其实，可以不用管变大还是变小。直接先down，后up。实际两个过程只会执行一个。

heap[k] = heap[size]; size --; down(k); up(k);

修改任意一个元素

先修改目标元素，然后down、up。

heap[k] = newVal; down(k); up(k);

代码实现

向下调整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int N = 1e5+10;
int h[N];
int cnt; // 堆的元素个数
// 时间复杂度：O(logn) 跟树的高度相关
void down(int u)
{
    
    int t = u;
    // 要将两个孩子节点中,值的最小的那个与当前节点交换
    // t保存的是值最小的节点的index
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    // 也可能u本身就是最小的，不用调整
    if (u != t)
    {
        swap(h[u], h[t]);
        down(t);
    }
}

向上调整

1
2
3
4
5
6
7
8
void up(int u)
{
    while (u / 2 > 0 && h[u] < h[u / 2])
    {
        swap(h[u], h[u / 2]);
        u >>= 1;
    }
}

建堆

从n/2开始down到0

1
for (int i = n / 2; i >= 1; -- i) down(i);

时间复杂度为O(n)O(n)

image-20211103164234732

假设是满二叉树情况，进行复杂度的分析。

此时，h[n/2]的节点是倒数第二层最后一个节点，从倒数第二层开始

倒数第二层有 n4\frac{n}{4} 个节点，每一个都要 down(k)down(k) 1次，则计算次数为n4×1\frac{n}{4}\times1

倒数第三层有 n8\frac{n}{8} 个节点，每一个节点都要 down(k)down(k) 2次，则计算次数为n8×2\frac{n}{8}\times2

所以总的计算次数：

CNT=n22×1+n23×2+n24×3+⋯=n×(122+223+324+⋯ )CNT = \frac{n}{2^2}\times1+\frac{n}{2^3}\times2+\frac{n}{2^4}\times3+\cdots=n\times(\frac{1}{2^2}+\frac{2}{2^3}+\frac{3}{2^4}+\cdots)

S=122+223+324+⋯S=\frac{1}{2^2}+\frac{2}{2^3}+\frac{3}{2^4}+\cdots

S=2S−S=12+122+123+⋯≤1S=2S-S=\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\cdots\le 1

CNT≤n×1=nCNT≤n\times1=n

这里也可以用级数的知识去做

例题

acwing 838. 堆排序

输入一个长度为 nn 的整数数列，从小到大输出前 mm 小的数。

只用到了向下调整down(k)

输入格式

第一行包含整数 nn 和 mm。

第二行包含 nn 个整数，表示整数数列。

输出格式

共一行，包含 mm 个整数，表示整数数列中前 mm 小的数。

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
#include <iostream>

using namespace std;

const int N = 1e5+10;

int h[N];
int cnt; // 记录当前堆的元素个数

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

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) {
        cin >> h[i];
    }
    cnt = n;
    // 建堆
    for (int i = n / 2; i >= 1; -- i) down(i);
    int k = 1;
    
    while (m --) {
        // 输出堆顶元素，即为最小值
        printf("%d ", h[1]);
        // 删除第一个堆顶元素：将最后一个元素覆盖h[1]，长度减1，然后down(1)
        h[1] = h[cnt];
        cnt --;
        down(1);
    }
    
    return 0;
}

acwing 839. 模拟堆

heap_swap()

image-20211106140438421
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
#include <iostream>
#include <cstring>

const int N = 1e5+10;

int h[N], ph[N], hp[N];
int cnt = 0;

using namespace std;
// 难点在于 heap_swap 交换顺序无所谓
// 输入的为堆h中的序号index
// pos 表示 索引数组中的序号--索引数组保存的是元素插入次序和在堆中的序号对应关系
// hp[index] = pos; heapIndex_to_indexArrayPos
// ph[pos] = index; indexArrayPos_to_heapIndex
void heap_swap(int x, int y) {
    swap(h[x], h[y]);
    swap(hp[x], hp[y]);
    swap(ph[hp[x]], ph[hp[y]]);
}
// 小根堆
// 向下调整
void down(int u) {
    int t = u;
    if (2 * u <= cnt && h[2 * u] < h[t]) t = 2 * u;
    if (2 * u + 1 <= cnt && h[2 * u + 1] < h[t]) t = 2 * u + 1;
    if (t != u) {
        heap_swap(u, t);
        down(t);
    }
}
// 向上调整
void up(int u) {
    while (u / 2 && h[u / 2] > h[u]) {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

int main() {
    int n;
    int pos = 0;
    cin >> n;
    while (n --) {
        //
        char type[5];
        scanf("%s", type);
        // 插入一个元素
        if (!strcmp(type,"I")) {
            int num;
            scanf("%d", &num);
            pos ++; // 插入次序+1
            cnt ++; //堆的size+1
            h[cnt] = num; // 更新h、hp、ph数组
            hp[cnt] = pos;
            ph[pos] = cnt;
            up(cnt); // 向上调整
        }
        if (!strcmp(type, "PM")) {
            int res;
            res = h[1];
            cout << res << endl;
        }// 删除堆顶元素
        if (!strcmp(type,"DM")) {
            heap_swap(1, cnt); // 将堆顶元素和堆最后一个元素交换
            cnt --; // cnt --
            down(1); // 从堆顶向下调整
        }
        if (!strcmp(type, "D")) {
            int pos, index;
            scanf("%d", &pos);
            index = ph[pos]; // 删除指定插入次序pos的元素，获取pos对应在堆h中的序号
            heap_swap(index, cnt);
            cnt --;
            up(index);
            down(index);
        }
        if (!strcmp(type, "C")) {
            int k, x;
            scanf("%d %d", &k, &x);
            k = ph[k]; // 改变指定插入次序pos的元素的值
            h[k] = x;
            up(k);
            down(k);
        }
    }
    return 0;
}

leetcode 剑指 Offer 41. 数据流中的中位数

问题描述：

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。

代码实现：

1、c++ stl中的优先队列

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
class MedianFinder {
public:
    // 最大堆，存储左边一半的数据，堆顶为最大值
    priority_queue<int, vector<int>, less<int>> maxHeap;
    // 最小堆， 存储右边一半的数据，堆顶为最小值
    priority_queue<int, vector<int>, greater<int>> minHeap;
    /** initialize your data structure here. */
    MedianFinder() {
    }

    // 维持堆数据平衡，并保证左边堆的最大值小于或等于右边堆的最小值
    void addNum(int num) {
        /*
         * 当两堆的数据个数相等时候，左边堆添加元素。
         * 采用的方法不是直接将数据插入左边堆，而是将数据先插入右边堆，算法调整后
         * 将堆顶的数据插入到左边堆，这样保证左边堆插入的元素始终是右边堆的最小值。
         * 同理左边数据多，往右边堆添加数据的时候，先将数据放入左边堆，选出最大值放到右边堆中。
         */
        if (maxHeap.size() == minHeap.size()) {
            minHeap.push(num);
            int top = minHeap.top();
            minHeap.pop();
            maxHeap.push(top);
        } else {
            maxHeap.push(num);
            int top = maxHeap.top();
            maxHeap.pop();
            minHeap.push(top);
        }
    }
    
    double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.top()+minHeap.top())*1.0/2;
        } else {
            return maxHeap.top()*1.0;
        }
    }
};
/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

手动实现大根堆和小根堆

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
class MedianFinder {
public:
    /** initialize your data structure here. */
    vector<int> minH;
    vector<int> maxH;
    int minCnt, maxCnt;
    // 最小堆的方法实现
    void minDown(int u) {
        int t = u;
        if (u*2 <= minCnt && minH[u*2] < minH[t]) t = u*2;
        if (u*2+1 <= minCnt && minH[u*2+1] < minH[t]) t = u*2+1;
        if (u != t) {
            swap(minH[u], minH[t]);
            minDown(t);
        }
    }

    void minUp(int u) {
        while (u / 2 && minH[u] < minH[u / 2]) {
            swap(minH[u], minH[u / 2]);
            u >>= 1;
        }
    }

    // 最大堆的方法实现
    void maxDown(int u) {
        int t = u;
        if (u*2 <= maxCnt && maxH[u*2] > maxH[t]) t = u*2;
        if (u*2+1 <= maxCnt && maxH[u*2+1] > maxH[t]) t = u*2+1;
        if (u != t) {
            swap(maxH[u], maxH[t]);
            maxDown(t);
        }
    }

    void maxUp(int u) {
        while (u / 2 && maxH[u] > maxH[u / 2]) {
            swap(maxH[u], maxH[u / 2]);
            u >>= 1;
        }
    }

    MedianFinder() {
        this->maxH = vector<int>(1, 0);
        this->minH = vector<int>(1, 0);
        minCnt = 0;
        maxCnt = 0;
    }
    
    void addNum(int num) {
        if (maxCnt == minCnt) {
            maxCnt ++;
            maxH.push_back(num);
            maxUp(maxCnt);

            int tmp = maxH[1];
            maxH[1] = maxH[maxCnt];
            maxCnt --;
            maxDown(1);
            maxH.pop_back();
        
            minCnt ++;
            minH.push_back(tmp);
            minUp(minCnt);
        }
        else {
            minCnt ++;
            minH.push_back(num);
            minUp(minCnt);

            int tmp = minH[1];
            minH[1] = minH[minCnt];
            minCnt --;
            minDown(1);
            minH.pop_back();

            maxCnt ++;
            maxH.push_back(tmp);
            maxUp(maxCnt);
        }
    }
    
    double findMedian() {
        if (minCnt == maxCnt) return (minH[1] + maxH[1]) / 2.0;
        else return 1.0 * minH[1];
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

📔博文图谱

提及本博文的链接