c++中堆的实现

在上周的一场周赛中，要用到堆，但是我并不知道如何初始化堆，虽然并没有很影响通过速度，但还是从大佬的代码中学到了很多：

普通堆的实现：

堆其实就是完全二叉树的线性存储形式

839. 模拟堆

c++
#include<bits/stdc++.h>
using namespace std;

const int N = 100010;

int h[N], ph[N], hp[N], cnt;
int n, idx = 0, x, c;
string op;

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 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= cnt && 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;
    }
}

int main()
{
    cin >> n;
    while(n--)
    {
        cin >> op;
        if(op == "I")
        {
            scanf("%d", &x);
            cnt++;
            idx++;
            ph[idx] = cnt, hp[cnt] = idx;
            h[cnt] = x;
            up(cnt);
        }
        else if(op == "D")
        {
            scanf("%d", &x);
            x = ph[x];
            heap_swap(x, cnt);
            cnt --;
            up(x);
            down(x);
        }
        else if(op == "C")
        {
            scanf("%d %d", &x, &c);
            x = ph[x];
            h[x] = c;
            up(x);
            down(x);
        }
        else if(op == "DM")
        {
            heap_swap(1, cnt);
            cnt--;
            down(1);
        }
        else
        {
            printf("%d\n", h[1]);
        }
    }
    return 0;
}

以上并不是本篇文章重点，代码下去自己背去，下边才是重点

优先队列：

声明：

c++
priority_queue<int> q;                              // 大根堆
priority_queue<int, vector<int>, greater<int>> q;   // 小根堆
priority_queue<pair<int, int>>q;

操作：

堆的函数：

C++的STL提供了make_heap、push_heap、pop_heap、sort_heap等算法，它们用来将一个随机存储的数组或者容器等转换为一个heap。

这里所说的转换为heap意思是将原来的存储顺序改变，将转换成的堆层序遍历后所得到的元素顺序作为数组或者容器新的元素顺序(实质上就是对原来的数据用一个算法换了一下元素顺序)。

1、make_heap

函数声明：

c++
template <class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>
void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

• make_heap的功能是将一段现有的数据转化成一个堆，默认情况下生成的是一个大堆。
• 在第一种声明中，参数为迭代器类型，当我们传入一个左闭右开的区间[first, last)时，它会自动把这个区间的数据转化成一个大堆。 在第二种声明中，多了一个模板参数，用于我们给他传入一个比较类型，用这个比较类型来实现小堆的转化。当我们想实现小堆转化时，首先要#include <functional>，然后参数中使用great<int>()，
• 需要注意的是当make_heap中使用了greater()后，后面pop_heap、push_heap和sort_heap都需要加上greater()。 生成大堆的代码：

2、push_heap

函数声明：

c++
template <class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>
void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

• push_heap的功能是往堆中插入一个数据。
• 它的默认前提是区间[first, last - 2]已经满足堆结构，并且要插入的数据已经插入到区间的最后一个位置。
• 对于基于vector生成的heap：

3、pop_heap

函数声明：

c++
template <class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

• pop_heap的功能也是实现调整工作，但是是删除前的调整。
• pop_head会将堆顶的元素与最后一个元素(注意最后一个元素是last的上一个元素)交换，然后再调整，将除了最后一个元素的剩余其他元素重新恢复成堆结构。需要注意的是每次pop一个元素后，下一次pop时就需要将区间缩小1(last减1)。

4、sort_heap

函数声明：

c++
template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

• sort_heap的功能就相当于多次调用heap_pop，
• 我们每次调用heap_pop都将栈顶元素与最后元素进行交换(将栈中最大元素与栈中最后一个元素交换)，然后last减1，重复调用heap_pop一直到只剩下1个元素，我们就实现了将元素排序。