堆模板

悠悠 2022-05-16 06:48 112阅读 0赞

小根堆 越小的整数优先级越大

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<queue> 
    using namespace std;
    priority_queue<int,vector<int> ,greater<int> >q;
    int main(){
        int n;
        scanf("%d",&n);
        while(n--){
            int flag,num;
            scanf("%d",&flag);
            if(flag==1){
                scanf("%d",&num);
                q.push(num);
            }
            else if(flag==2){
                printf("%d\n",q.top());
            }
            else{
                q.pop();
            }
        }
        return 0;
    }

STL版

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int heap_size;
    int heap[1000005];
    void put(int x)
    {
     heap[++heap_size]=x;
     push_heap(heap+1,heap+1+heap_size,greater<int>());  
    }
    int get()
    {    
     return heap[1];   
    }
    void del()
    { 
     pop_heap(heap+1,heap+1+heap_size,greater<int>());  
     heap_size--;    
    }
    int main()
    {
     int n;
     scanf("%d",&n);
     int x;
     for(int i=1;i<=n;i++)
     {
      scanf("%d",&x);
      if(x==1) {
       scanf("%d",&x);put(x);}
      else if(x==2) {
       printf("%d\n",get());}
      else if(x==3) del();      
     }
    }

手打版 [点我][Link 1]

[Link 1]: https://www.luogu.org/blog/27114/solution-p3378

发表评论取消回复

表情：

评论列表（有 0 条评论，112人围观）

还没有评论，来说两句吧...

相关阅读

相关对顶堆模板！！【DS对顶堆】ABC281 E - Least Elements

我想的思路和正解是差不多的就是滑动窗口，每过去一个用DS维护一下前k个元素和sum 本来想的是用优先队列维护前k个然后想着multiset维护前k个，但是具体不知道怎

￡神魔★判官ぃ/ 2024年03月22日 10:42/ 0 赞/ 91 阅读

相关天梯题集——关于堆的判断（小顶堆模板题、模拟构造过程）

> 堆是一种常用的树形结构，是一种特殊的完全二叉树，当且仅当满足所有节点的值总是不大于或不小于其父节点的值的完全二叉树被称之为堆。 > 堆的这一特性称之为堆序性。因此，在一

「爱情、让人受尽委屈。」/ 2022年12月23日 15:24/ 0 赞/ 173 阅读

相关堆排序模板

public class Main { public static void main(String[] args) {

淩亂°似流年/ 2022年10月06日 08:52/ 0 赞/ 120 阅读

相关 hdu 2544 单源最短路问题 dijkstra+堆优化模板

最短路 Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Other

水深无声/ 2022年08月03日 00:11/ 0 赞/ 218 阅读

相关 C++模板堆排序

堆排序简介堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小

爱被打了一巴掌/ 2022年07月28日 01:03/ 0 赞/ 133 阅读

相关 C++实现一个堆（模板）

堆是一个很基础的数据结构，在stl里面有封装`make_heap`、`push_heap`等操作，这两天看到libevent用小根堆实现Timer，就想实现一个简单的堆。

àì夳堔傛蜴生んèń/ 2022年06月15日 00:00/ 0 赞/ 121 阅读

相关最短路 + 邻接表 + 堆优化（模板）（Dijkstra + SPFA）

-------------------- 模板已经过题目验证 -------------------- 最短路模板+邻接表建图+堆优化(优先队列) 复杂度O(Elog(E

秒速五厘米/ 2022年06月07日 12:50/ 0 赞/ 237 阅读

相关堆模板

小根堆越小的整数优先级越大 include<iostream> include<cstdio> include<algorithm> inc

悠悠/ 2022年05月16日 06:48/ 0 赞/ 113 阅读

相关 (模板)堆的快速搭建

堆排序是指使用堆结构对一个序列进行排序的过程,此处讨论递增排序的情况考虑对一个堆来说,堆顶元素是最大的,因此在建堆完毕后,思路就是取出堆顶元素,然后将堆的最后一个元素替换至

「爱情、让人受尽委屈。」/ 2022年04月18日 05:18/ 0 赞/ 128 阅读

相关堆模板

include<bits/stdc++.h> using namespace std; int tail=1,a[100]; void inse

梦里梦外;/ 2022年03月20日 04:18/ 0 赞/ 133 阅读