【题解】Luogu P3378 【【模板】堆】

这里封装了STL的函数来实现堆

如果开了O2优化,STL效率实在恐怖

首先STL提供了几个函数来实现堆

make_heap(),push_heap(),pop_heap(),sort_heap()

位于头文件algorithm中,

前三个函数会详解,后面一个略讲

void make_heap(first_pointer,last_pointer,compare_function)

将一个有数据的容器(vector,数组等)转换为一个堆

复杂度为最多O(3n)

第一个参数是首指针,后面是尾指针,第三个是比较器,缺省时建立大根堆,用greater<T>()可以建立小根堆

 

void push_heap(first_pointer,last_pointer,compare_function)

push_heap(),假设[first,last – 1)是有效的堆(空堆也是有效的),然后把新的元素加入堆,将[first,last)做成一个堆

 

void pop_heap(first_pointer,last_pointer,compare_function)

pop_heap(),它不是真正的把元素弹出,只是把first和last交换,然后再把[first,last – 1)做成一个堆,如果想要删除请用pop_back()

 

实现代码:这里把这几个函数封装成一个类,方便使用(尽管许多操作没有实现,不过A模板就够用了)。

#include<cstdio>
#include<algorithm>
#include<vector>
#include<functional>

namespace OI{
    using std::vector;
    using std::greater;
    using std::make_heap;
    using std::pop_heap;
}

using namespace OI;

template<class T>
class Heap{
    public:vector<T> v;
    
    public:Heap(){
        v.reserve(1000000);
    }
    public:~Heap(){}
    
    public:void push(T key){
        v.push_back(key);
        push_heap(v.begin(),v.end(),greater<T>());
    }
    
    public:void pop(){
        pop_heap(v.begin(),v.end(),greater<T>());
        v.pop_back();
    }
    
    public:T front(){
        return v[0];
    }
};

int main(){
    int op,key,n;
    scanf("%d",&n);
    
    Heap<int> h;
    
    while(n--){
        scanf("%d",&op);
        if(op == 1){
            scanf("%d",&key);
            h.push(key);
        }else if(op == 2){
            printf("%d\n",h.front());
        }else if(op == 3){
            h.pop();
        }
    }
    
    return 0;
}

无O2优化

O2优化

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注