1.核心思想

堆是一颗完全二叉树，用一个数组维护，下标为 x 的结点左儿子下标 2*x，右儿子下标 2*x + 1【当然前提是根结点下标从1开始】

2. 堆能支持的操作

(1) 插入一个数
(2) 求集合中的最小（大）值
(3) 删除最小值
(4) 删除任意一个数
(5) 修改任何一个数

易错点：

(1) 练习出过取前n最小值直接输出下标1-n的堆元素, 没有深刻理解堆的定义，堆只保证根节点小（大）于左右儿子的节点，但是最小的数并不是按顺序排列；正确的输出应该是每取一个最小值，就需要删除堆顶元素，down(1), 继续取堆顶元素

(2) 练习错误2: 当下标从 1开始，父节点下标 u， 左右儿子节点的下标是 2u、2u+1, 不是 2u+1, 2u+2

3. 代码模板（小根堆为例）

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

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

(1) 插入一个数：heap[++size] = x; up(size);
(2) 求集合最小值：heap[1]
(3) 删除最小值： heap[1] = heap[size]; size --; down(1);
(4) 删除任意一个数：heap[k] = heap[size]; size --; down(k); up(k);
(5) 修改任意一个数：heap[k] = x; down(k); up(k);

(6) 将一个长度为n的数组num构造成堆的O(n)的方法
for(int i = n / 2; i; i--){
    down(i);
}

题目描述举例

输入一个长度为n的整数数列，从小到大输出前m小的数。
输入格式

第一行包含整数n和m。

第二行包含n个整数，表示整数数列。
输出格式

共一行，包含m个整数，表示整数数列中前m小的数。
数据范围

1≤m≤n≤105
，
1≤数列中元素≤109

样例

输入样例：

5 3
4 5 1 3 2

输出样例：

1 2 3

C 代码

#include<stdlib.h>
#include<stdio.h>

#define N 100010
int heap[N], size;

int n, m;

void down(int u)
{
    int t = u;
    if(2*u <= size && heap[2*u] < heap[t]) t = 2*u;
    if(2*u + 1 <= size && heap[2*u + 1] < heap[t]) t = 2*u + 1;

    if(t != u){
        int tmp = heap[u];
        heap[u] = heap[t];
        heap[t] = tmp;

        down(t);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    size = n;
    for(int i = 1; i <= n; i++){
        scanf("%d", &heap[i]);
    }

    // init heap
    for(int i = n / 2; i; i--){
        down(i);
    }

    while(m--){
        printf("%d ", heap[1]);

        heap[1] = heap[size];
        size --;
        down(1);
    }
}