数据结构_堆

堆

模拟思路：

• 几个基本操作：up and down

void down(int u) {
    int t = u;
    if(u * 2 <= siz && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= siz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(u != t){
        heap_swap(u, t);
        down(t);
    }
}

void up(int u) {
    while(u / 2 && h[u / 2] > h[u]) {
        heap_swap(u, u / 2);
        u /= 2;
    }
}

• 从数组下标为1开始存储，当前位置的左孩子的下标为当前位置的下标i * 2,右孩子子的下标为当前位置的下标i * 2 + 1
• 创建小顶堆

    for(int i = 1; i <= n; i++) scanf("%d",&h[i]);
    siz = n;
    for(int i = n / 2; i; i--) down(i);

• 最小元素： h[1]
• 插入元素：先将其插到末尾，然后up(siz)
• 删除最小元素： 将末尾元素与h[1]交换，然后down(1)

堆排序

代码模板

const int N = 1e6 + 10;
int h[N],n,m,siz;
void down(int u) {
    int t = u;
    if(u * 2 <= siz && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= siz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(t != u) {
        swap(h[t], h[u]);
        down(t);
    }
}

void heap_sort(int m) {
    for(int i = 1; i <= n; i++) scanf("%d",&h[i]);
    siz = n;
    for(int i = n / 2; i; i--) down(i);
    while(m--) {
        printf("%d ",h[1]);
        h[1] = h[siz];
        siz--;
        down(1);
    }
}