[洛谷]P3378 【模板】堆
方法一 手寫堆
- 最小堆插入
從新增的最后一個結點的父結點開始，用要插入元素向下過濾上層結點（相當于要插入的元素向上滲透）
void siftdown(int i) //傳入一個需要向下調整的結點編號i，這里傳入1，即從堆的頂點開始向下調整
{
int t,flag=0;//flag用來標記是否需要繼續向下調整
//當i結點有兒子的時候（其實是至少有左兒子的情況下）并且有需要繼續調整的時候回圈窒執行
while( i*2<=n && flag==0 )
{
//首先判斷他和他左兒子的關系，并用t記錄值較小的結點編號
if( h[ i] > h[ i*2] )
t=i*2;
else
t=i;
//如果他有右兒子的情況下，再對右兒子進行討論
if(i*2+1 <= n)
{
//如果右兒子的值更小，更新較小的結點編號
if(h[ t] > h[ i*2+1])
t=i*2+1;
}
//如果發現最小的結點編號不是自己，說明子結點中有比父結點更小的
if(t!=i)
{
swap(t,i);//交換它們，注意swap函式需要自己來寫
i=t;//更新i為剛才與它交換的兒子結點的編號，便于接下來繼續向下調整
}
else
flag=1;//則否說明當前的父結點已經比兩個子結點都要小了，不需要在進行調整了
}
}
- 最小堆洗掉
void siftdown(int i) //傳入一個需要向下調整的結點編號i，這里傳入1，即從堆的頂點開始向下調整
{
int t,flag=0;//flag用來標記是否需要繼續向下調整
//當i結點有兒子的時候（其實是至少有左兒子的情況下）并且有需要繼續調整的時候回圈窒執行
while( i*2<=n && flag==0 )
{
//首先判斷他和他左兒子的關系，并用t記錄值較小的結點編號
if( h[ i] > h[ i*2] )
t=i*2;
else
t=i;
//如果他有右兒子的情況下，再對右兒子進行討論
if(i*2+1 <= n)
{
//如果右兒子的值更小，更新較小的結點編號
if(h[ t] > h[ i*2+1])
t=i*2+1;
}
//如果發現最小的結點編號不是自己，說明子結點中有比父結點更小的
if(t!=i)
{
swap(t,i);//交換它們，注意swap函式需要自己來寫
i=t;//更新i為剛才與它交換的兒子結點的編號，便于接下來繼續向下調整
}
else
flag=1;//則否說明當前的父結點已經比兩個子結點都要小了，不需要在進行調整了
}
}
//洗掉最小數
void del(){
dui[1]=dui[d];
d--;
shitdown(1);
}
方法二 STL
c++優先佇列(priority_queue)用法詳解
#include<bits/stdc++.h>
using namespace std;
int n,d;
int main(){
priority_queue<int,vector<int>,greater<int> > dui;
cin>>n;
for(int i=1;i<=n;i++){
int op;
cin>>op;
if(op==1){
int num;
cin>>num;
dui.push(num);
}
else if(op==2)
cout<<dui.top()<<endl;
else if(op==3)
dui.pop();
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/556833.html
標籤：其他
上一篇：讓golang程式生成coredump檔案并進行除錯
下一篇：返回列表