【數據結構】 堆（二叉堆）詳解
定義：
堆的底層數據結構是樹，一般不引起歧義的情況下，堆指的是二叉堆，其底層數據結構是完全二叉樹，堆分為大根堆和小根堆，大根堆的每個節點的父親都大于當前節點，小根堆反之，本文以小根堆為例
二叉堆插入
思路：將要插入的樹放在數組最后，令數組原來的大小為 \(size\) ，堆數組的名為 \(heap\) ，則 \(heap[++size]=x\) ，其中 \(x\) 為要插入的數字，之后將插入的數字不斷向上調整即可（如圖）
CODE:
void put(int x){
heap[++size]=x;
int now=size;
while (now>1&&heap[now/2]>heap[now]){
swap(heap[now/2],heap[now]);
now/=2;
}
}
時間復雜度： \(O(\log n)\)
二叉堆刪除
思路：將要刪除的元素與最后一個元素交換，同時 \(size--\) ，再將這個位置的樹向下調整
CODE:
void del(int idx){
swap(heap[size],heap[idx]);
size--;
while (idx*2<=size){
int t=idx;
idx*=2;
if (idx+1<=size&&heap[idx]>heap[idx+1]) idx++;
if (heap[idx]>=heap[t]) return ;
swap(heap[t],heap[idx]);
}
}
時間復雜度： \(O(\log n)\)
例題
[NOIP2004 提高組] 合并果子
例題代碼：
點擊查看代碼
#include<cstdio>
#include<algorithm>
using namespace std;
int n,heap[10005],size,ans;
void put(int x){
heap[++size]=x;
int now=size;
while (now>1&&heap[now/2]>heap[now]){
swap(heap[now/2],heap[now]);
now/=2;
}
}
void del(int idx){
swap(heap[size],heap[idx]);
size--;
while (idx*2<=size){
int t=idx;
idx*=2;
if (idx+1<=size&&heap[idx]>heap[idx+1]) idx++;
if (heap[idx]>=heap[t]) return ;
swap(heap[t],heap[idx]);
}
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
int tmp;
scanf("%d",&tmp);
put(tmp);
}
for (int i=1;i<n;i++){
int a=heap[1];
del(1);
int b=heap[1];
del(1);
put(a+b);
ans+=a+b;
}
printf("%d",ans);
return 0;
}
浙公網安備 33010602011771號