手写二叉堆

#include <bits/stdc++.h> 
using namespace std;
template<typename T,typename Comp=greater<int>>
struct heap{
    vector<T>tree{1};
    int n=0;
    Comp comp;
    heap(Comp cmp=Comp{}):comp(cmp){}
    T top(){
    	return tree[1];
	}
    void push(T x){
        n++;
        tree.push_back(x);
        int pthis=n,parent=n/2;
        while (parent>=1&&comp(tree[pthis],tree[parent])){
            swap(tree[pthis], tree[parent]);
            pthis=parent;
            parent/=2;
        }
    }
    void pop(){
        swap(tree[1],tree[n]);
        tree.pop_back();
        n--;
        int pthis=1;
        while(pthis*2<=n){
            int left=pthis*2,right=pthis*2+1;
            int minchild=left;
            if(right<=n&&comp(tree[right],tree[left])){
                minchild=right;
            }
            if(comp(tree[minchild],tree[pthis])){
                swap(tree[pthis],tree[minchild]);
                pthis=minchild;
            }else break;
        }
    }
};
int n,op,t;
int main(){
	heap<int,less<int>> pq;
	cin>>n;
	while(n--){
		cin>>op;
		switch (op){
			case 1:
				cin>>t;
				pq.push(t);
				break;
			case 2:
                cout<<pq.top()<<endl;
				break;
			case 3:
                pq.pop();
				break;
		}
	}
	return 0;
}

二叉堆（封装好的）:

template<typename T,typename Comp=less<T>>
struct heap{
    std::vector<T> tree{1};
    int n=0;
    Comp comp;
    heap(Comp cmp=Comp{}):comp(cmp){}
    T top(){
    	return tree[1];
	}
    void push(T x){
        n++;
        tree.push_back(x);
        int pthis=n,parent=n/2;
        while (parent >= 1 && comp(tree[pthis], tree[parent])){
            std::swap(tree[pthis], tree[parent]);
            pthis = parent;
            parent /= 2;
        }
    }
    void pop(){
        swap(tree[1],tree[n]);
        tree.pop_back();
        n--;
        int pthis=1;
        while(pthis*2<=n){
            int left=pthis*2,right=pthis*2+1;
            int minchild=left;
            if(right<=n&&comp(tree[right],tree[left])){
                minchild=right;
            }
            if(comp(tree[minchild],tree[pthis])){
                swap(tree[pthis],tree[minchild]);
                pthis=minchild;
            }else break;
        }
    }
};

前言

小清新题解，没有过多复杂的图片和文字。

解题思路

数据结构题，我们使用 STL 库里的优先队列。

定义一个最小值优先的优先队列，它是一个最小堆，即队列顶部始终是队列中最小的元素。然后，读取输入的一个整数 $n$，表示接下来将进行 $n$ 次操作。

• $op=1$：将 $t$ 插入到最小堆中。
• $op=2$：输出当前最小堆的顶部元素。
• $op=3$：删除最小堆的顶部元素。

依照以上文字进行模拟即可。

解题代码

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

int n, op, t;
priority_queue<int, vector<int>, greater<int>> pq;

int main()
{
	cin >> n;
	while (n--)
	{
		cin >> op;
		switch (op)
		{
			case 1:
				cin >> t;
				pq.push(t);
				break;
			case 2:
                cout << pq.top() << endl;
				break;
			case 3:
                pq.pop();
				break;
		}
	}
	return 0;
}

推荐习题

如果还想练习“堆”这种数据结构的可以参考以下习题：

• P1090 [NOIP 2004 提高组] 合并果子
• P1628 合并序列
• P1801 黑匣子
• P1168 中位数