heap 算法函数

这一系列函数是在做 这道题 时发现的

这道题空间卡的很死，是不能用数组存下所有数字进行快排的

后来又尝试用 \(multiset\) 优化空间，发现不行，可能是 \(multiset\) 还有结构性存储空间

遂再尝试插排，时间又过不了...

后来发现了 \(heap\) 系列函数可以做这道题，一方面可以支持对数组或者 \(vector\) 等存储空间较小的容器进行操作，一方面时间复杂度也与 \(multiset\) 方法一样

这里介绍一下 \(heap\) 系列函数

make_heap

make_heap 函数将现有的数据转化为一个(默认最大)堆

vector<int> vec = {1, 2, 3, 4};

make_heap(vec.begin(), vec.end());   // vec : 4 2 3 1

make_heap(vec.begin(), vec.end(), greater<int>());   // 最小堆，这里 greater<int> 后面加 () 是模板类生成一个临时对象传入 make_heap 函数

// 若使用 greater<int>() 构建最小堆，之后的函数都要加上 greater<int>()

push_heap

在堆的末尾添加一个元素后，通过 push_heap 对容器进行维护使其满足堆性质

注意，使用这个函数需要保证除了新添加的元素，之前的元素已经构成了一个堆

vector<int> vec = {1, 2, 3, 4};

make_heap(vec.begin(), vec.end());

vec.push_back(5);                       // 堆末尾添加新元素

push_heap(vec.begin(), vec.end());  // 维护堆，堆结构大小 +1

pop_heap

将堆头元素弹出(具体实现是将堆头元素与堆尾元素交换)并再次调整，使得剩下的 \(n-1\) 个元素重新满足堆结构

vector<int> vec = {1, 2, 3, 4};

pop_heap(vec.begin(), vec.end());   // 堆顶弹出，堆结构大小 -1

sort_heap

sort_heap 的功能就相当于多次调用 heap_pop 直到堆为空，这样就实现了对元素的排序

用 heap 系列函数再来解决以上问题就方便多了，贴下代码

#include <iostream>

#include <algorithm>

using namespace std;

const int MAX_N = 1e5 + 1;

int a[MAX_N];

int main() {

    int n, k;

    cin >> n >> k;

    for (int i = 1; i <= k; ++i)    cin >> a[i];

    make_heap(a + 1, a + k + 1);

    for (int i = 1; i <= n - k; ++i) {

        int x;

        cin >> x;

        if (x >= a[1])  continue;

        a[k + 1] = x;

        push_heap(a + 1, a + k + 2);

        pop_heap(a + 1, a + k + 2);

    }

    cout << a[1] << endl;

    return 0;

}

heap 算法函数的相关教程结束。