利用vector

#include <algorithm>

make_heap : 指定迭代器区间和一个可选的比较函数创建一个堆 o(n)
push_heap : 指定区间最后一个元素加入到heap中 o(log n)
pop_heap : 弹出堆顶元素，放置在区间末尾 o(log n)
sort_heap : 堆排序算法，反复调用pop_heap实现 o(nlog n)
is_heap : 判断给定区间是否是一个heap o(N)
`is_heap_until : 找出区间中第一个不满足heap条件的位置``

利用优先队列priority_queue

参考

priority_queue其实是对make_heap的封装。

push //插入元素，并对底层容器排序

emplace //原位构造元素并底层排序

pop //删除第一个元素

#include <functional>
#include <queue>
#include <vector>
#include <iostream>
 
template<typename T> void print_queue(T& q) {
    while(!q.empty()) {
        std::cout << q.top() << " ";
        q.pop();
    }
    std::cout << '\n';
}

int main() {
    std::priority_queue<int> q;
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q.push(n);
 
    print_queue(q);
 
    std::priority_queue<int, std::vector<int>, std::greater<int> > q2;
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q2.push(n);
 
    print_queue(q2);
 
    // 用 lambda 比较元素。
    //自定义比较函数：与1异或值大的排在前列
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1);};
    std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q3.push(n);
 
    print_queue(q3);
 
}
/*
输出：
9 8 7 6 5 4 3 2 1 0 
0 1 2 3 4 5 6 7 8 9 
8 9 6 7 4 5 2 3 0 1
*/

C++ STL实现堆

利用vector

利用优先队列priority_queue

FEATURED TAGS

FRIENDS