[洛谷]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;
}