文章目錄

• 二叉堆
• • 概述
  • 插入
  • • 代碼
  • 訪問
  • • 代碼
  • 完整代碼
• 優先隊列：priority_queue
• • • 基本用法
    • 小根堆的聲明：
    • 結構體
    • 注意
• Thanks for reading！

二叉堆

概述

為什么不用pq呢
算比較簡單的數據結構了
它可以用log的時間復雜度插入元素和訪問（取出）最大（小）值（最大和最小只能取一個！）
缺點是除了干這個基本沒有別的延伸用法。。。
主要性質（以大根堆為例，小根堆反過來就行）：
1.是一棵二叉樹(廢話）
2.爸爸結點永遠比兒子大（核心性質）
具體來看看代碼實現吧~

插入

先把新元素放在隊尾
只要沒有到堆頂就不斷嘗試和爸爸交換；
如果比它的爸爸大，就可以交換

代碼

void put(int k){tree[++len]=son;//先放在隊尾int son=len;while(son>1){//只要沒有到堆頂就不斷嘗試和爸爸交換：如果比它的爸爸大，就交換int fa=son>>1;if(tree[fa]>tree[son]) return;//如果比爸爸小的話就可以結束交換了swap(tree[fa],tree[son]);son=fa;}return; }

訪問

先取出堆頂的最大值
把當前的隊尾填到隊首的位置
只要有兒子就不斷嘗試與兒子交換
如果比兒子中任何一個小，就與其交換

代碼

int get(){int res=tree[1];//先取出堆頂的最大值tree[1]=tree[len--];//把當前的隊尾填到隊首的位置int fa=1;while(2*fa<=len){//只要有兒子就不斷嘗試與兒子交換:如果比兒子中任何一個小，就與其交換int son=2*fa;if(son<len&&tree[son]<tree[son+1]) son++;//找到較大的那個兒子if(tree[son]<tree[fa]) break;swap(tree[son],tree[fa]);fa=son;}return res; }

完整代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define mem(a,b) memset(a,b,sizeof(a)) const int N=1e5+100; int tree[N]; int n,len; int flag,x; void put(int k){tree[++len]=k;//先放在隊尾int son=len;while(son>1){//只要沒有到堆頂就不斷嘗試和爸爸交換：如果比它的爸爸大，就交換int fa=son>>1;if(tree[fa]>tree[son]) return;//如果比爸爸小的話就可以結束交換了swap(tree[fa],tree[son]);son=fa;}return; } int get(){int res=tree[1];//先取出堆頂的最大值tree[1]=tree[len--];//把當前的隊尾填到隊首的位置int fa=1;while(2*fa<=len){//只要有兒子就不斷嘗試與兒子交換:如果比兒子中任何一個小，就與其交換int son=2*fa;if(son<len&&tree[son]<tree[son+1]) son++;//找到較大的那個兒子if(tree[son]<tree[fa]) break;swap(tree[son],tree[fa]);fa=son;}return res; } int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&flag);if(flag==1){scanf("%d",&x);put(x);}else printf("%d\n",get());}return 0; }

優先隊列：priority_queue

基本用法

priority_queue
需要頭文件：queue
有這東西寫什么二叉樹啊
具體用法：

聲明：priority_queue q;
插入元素：q.push(x);
訪問堆頂：q.top()；
彈出堆頂：q.pop();

以下是之前那段代碼使用pq的版本：

int main(){scanf("%d",&n);priority_queue<int>q;for(int i=1;i<=n;i++){scanf("%d",&flag);if(flag==1){scanf("%d",&x);q.push(x);}else{printf("%d\n",q.top());q.pop();}}return 0; }

簡便程度不言而喻

小根堆的聲明：

priority_queue<int,vector<int>,greater<int> （注意這里必須有個空格！）> q;

結構體

也可以用結構體，只是需要重載一下運算符 <：

struct node{int value;bool operator < (const node y)const{return value<y.value;}; }; int main(){priority_queue<node>q;int v;node o;q.push((node){v});//這里就是看個具體操作的用法，具體怎么操作看你需求啦~o=q.front();q.pop();return 0; }

注意

1.當你已經pop完所有元素再取堆頂時，它會一直給你彈出的最后一個

2.而當你根本沒push就直接訪問top時，會直接RE

Thanks for reading！

總結

以上是生活随笔為你收集整理的理解至上：二叉堆与优先队列详细用法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。