【堆--大根堆/小根堆】

大根堆

根节点的值为最大值

小根堆

根节点的值为最小值

优先队列的底层是用堆来实现的。
C++中STL中的优先队列默认的是大根堆，如果要用小根堆则需要加入greater.
优先队列 priority_queue。

大根堆
> priority_queue Q;
> priority_queue, less > Q;
小根堆
> priority_queue, greater > Q;

Q.push(x):将x入队  O(logN)
Q.top():获取队首元素  O(1)
Q.pop():队首元素出队 O(logN)
Q.empty():检查是否为空  若为空，返回True。O(1)
Q.size(): O(1)

#include
#include
using namespace std;
int main()
{
    // priority_queue Q;  // 大根堆
    // priority_queue, less > Q; // 大根堆
    priority_queue, greater > Q; // 小根堆
    Q.push(2);
    Q.push(6);
    Q.push(5);
    cout << Q.top();
}

代码展示 C++/STL/vector建堆。

vector v;
建堆
> make_heap(v.begin(), v.end(), less()); 大根堆
> make_heap(v.begin(), v.end(), greater()); 小根堆
push_heap()和pop_heap() 默认大根堆
> push_heap(v.begin(), v.end()); 
> push_heap(v.begin(), v.end(), greater() ); // 小根堆
> pop_heap(v.begin(), v.end(), greater()); // 小根堆

pop_heap()
> 默认大根堆；
> 将第一个元素从堆中删除，堆自动调整并将将删除的元素放到最后。

求第k大的数
选用大根堆实现

#include
#include
#include
using namespace std;
int main()
{
    int a[] = {29,23,15,26,51,19,12,35,40};
    // 51 40 35 29 26 23 19 15 12
    vector v;
    v.assign(a, a + 9);
    make_heap(v.begin(), v.end());
    // make_heap(v.begin(), v.end(), less());
    int k = 3, res;
    for(int i = 0; i < k; i++)
    {
        pop_heap(v.begin(), v.end());
        // pop_heap(v.begin(), v.end(), less());
        res = v[v.size() - 1];
        v.pop_back();
    }
    cout << res << 'n';
}

求第k小的数
选用小根堆实现

#include
#include
#include
using namespace std;
int main()
{
    int a[] = {29,23,15,26,51,19,12,35,40};
    // 51 40 35 29 26 23 19 15 12
    vector v;
    v.assign(a, a + 9);
    make_heap(v.begin(), v.end(), greater());
    int k = 3, res;
    for(int i = 0; i < k; i++)
    {
        pop_heap(v.begin(), v.end(), greater());
        res = v[v.size() - 1];
        v.pop_back();
    }
    cout << res << 'n';
}