OI

【模板】二叉堆、堆排序

堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
const int N=1000005;
int heap[N];//定义一个数组来存堆
int siz=0;//堆的大小 

void push(int x){//要插入的数 
    heap[++siz]=x;
    int now=siz;
    //插入到堆底 
    while(now){//还没到根节点，还能交换 
        int nxt=now>>1;//找到它的父亲 
        if(heap[nxt]>heap[now])swap(heap[nxt],heap[now]);//父亲比它大，那就交换 
        else break;//如果比它父亲小，那就代表着插入完成了 
        now=nxt;//交换 
    }
    return; 
}

void pop(){
    swap(heap[siz],heap[1]);siz--;//交换堆顶和堆底，然后直接弹掉堆底 
    int now=1;
    while((now<<1)<=siz){//对该节点进行向下交换的操作 
        int nxt=now<<1;//找出当前节点的左儿子 
        if(nxt+1<=siz&&heap[nxt+1]<heap[nxt])nxt++;//看看是要左儿子还是右儿子跟它换 
        if(heap[nxt]<heap[now])swap(heap[now],heap[nxt]);//如果不符合堆性质就换 
        else break;//否则就完成了 
        now=nxt;//往下一层继续向下交换 
    }
}

int top(){
    return heap[1];
}

堆排序

好像比较鸡肋
没有涉及到插入，删除元素操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<stdio.h>
#include<stdlib.h>
int heap[20000]={0};
void sift(int k,int n){
    int i=k,j=2*i,f=0;
    int x=heap[k];
    while(!f&&j<=n){
      if(heap[j]>heap[j+1]&&j<n)
        j++;
      if(x<heap[j])f=1;
      else{
        heap[i]=heap[j];
        i=j;
        j=2*i;
      }
    }
    heap[i]=x;
}
void hp(int n){
    int i,t;
    for(i=n/2;i>0;i--)
      sift(i,n);
    for(i=n;i>=2;i--){
      t=heap[1];
      heap[1]=heap[i];
      heap[i]=t;
      sift(1,i-1);
    }
}
int main(){
    int i,n;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
      scanf("%d",&heap[i]);
    hp(n);
    for(i=1;i<=n;i++)
      printf("%d ",heap[i]);
    printf("\n");
    return 0;
}