堆

堆是一颗完全二叉树,除了最底层之外其他层结点都是满的.这里我们取小根堆,有如下性质:

1.若k为某结点编号,其父结点编号为k/2,左子节点2k,右子节点2k+1

2.堆结点A若有子节点,则A的值小于(两个)子节点的值(若是大根堆就变成大于),两个子节点的值的大小不管

3.堆顶一定为堆中最小值(性质2的推论)

4.堆底层存满时时第二层元素为n/4个

堆的存储:

int heap[N], idx;

由于堆是一颗完全二叉树故可正好占满一个序列的位置,所以用数组存,idx代表用到点的个数.一般点要从1开始用(后文解释).

堆的一般操作:

1.down

down(t)代表把t元素下移,希望把t移到符合堆性质的位置.具体实现是比较t元素与其子节点值的大小(如果存在),假设存在a,b子节点,若t值小于a大于b则与t与a交换,若t值小于a小于b且b比a小则与b交换,这样逐渐向下直到字节点a’,b’的值都大于t为止.

t的值是堆中元素的下标.

void down(int k) {
    int t = k;
    if (2 * k <= idx && heap[2 * k] < heap[t]) t = 2 * k; //注意这里如果点从0开始用2*0还是0,不方便
    //!注意这里是heap[2 * k] < heap[t] 如果写成heap[2 * k] < heap[k] 就只跟k节点比大小了,没跟两个子节点没比大小
    if (2 * k + 1 <= idx && heap[2 * k + 1] < heap[t]) t = 2 * k + 1;
    if (t != k) {//t值不等于k值时,意味着可以交换/下移
        swap(heap[t], heap[k]);
        down(t);//由于是一颗完全二叉树,1e9的元素也不过三十层,所以直接递归
    }
}

2.up

up(t)代表把t元素上移,希望把t移到符合堆性质的位置.与down类似但相反,具体实现是比较t元素与其父节点值的大小(如果存在),若大于父节点值则交换,直到父节点值小于t/不存在父节点为止.

t的值是堆中元素的下标.

void up(int k) {
    while (k / 2 && heap[k / 2] > heap[k]) {
        swap(heap[k], heap[k / 2]);
        k /= 2;
    }
}

3.建堆

建堆之前肯定是要输入元素的.注意点从1开始标号.

有一种O(n)的建堆方法:从所给数据的中点n/2开始向前遍历,遍历一个元素t就down(t).为什么是正确的?因为若从1开始标号,n/2正好是第二层结点,n/2元素右侧如果有结点是不需要down的,因为他们没有子结点而且是底层;又由于最后一层结点大小不管,只需要down包括n/2及前面的元素(可以手画一下),第二层元素(期望n/4个)最多down一次,第三层最多down两次,每层结点都是子节点数的1/2,有

$$\frac{\mathrm{n}}{4}+2\cdot \frac{\mathrm{n}}{8}+3\cdot \frac{\mathrm{n}}{16}+\cdot \cdot \cdot +\left( \mathrm{n}-1 \right) \frac{\mathrm{n}}{2^{n+1}}\sim \mathrm{O}\left( \mathrm{n} \right) $$

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

4.堆顶删除

先让堆顶heap[1] = heap[idx]堆尾,那么堆顶值就被删了,然后堆中此时有两个值为heap[idx]的元素,此时令idx–,那么堆尾元素就被删了,剩下原来堆顶元素的位置的值等于原堆尾,此时down(heap[1])即可.弹出堆顶等价于输出最小值,所以也相当于排序.

heap[1] = heap[idx];
idx--;
down(1);//down(t),t的值是堆中元素的下标.

例题:

https://www.acwing.com/problem/content/840/
输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。
输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数，表示整数数列。
输出格式
共一行，包含 m 个整数，表示整数数列中前 m 小的数。
数据范围
1≤m≤n≤105，
1≤数列中元素≤109
输入样例：
5 3
4 5 1 3 2
输出样例：
1 2 3

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int heap[N], idx;
int a[N];
void down(int k) {
    int t = k;
    if (2 * k <= idx && heap[2 * k] < heap[t]) t = 2 * k;  
    //!注意这里是heap[2 * k] < heap[t] 如果写成heap[2 * k] < heap[k] 就只跟k节点比大小了,没跟两个子节点没比大小
    if (2 * k + 1 <= idx && heap[2 * k + 1] < heap[t]) t = 2 * k + 1;
    if (t != k) {
        swap(heap[t], heap[k]);
        down(t);//由于是一颗完全二叉树,1e9的元素也不过三十层,所以直接递归
    }
}
void up(int k) {
    while (k / 2 && heap[k / 2] > heap[k]) {
        swap(heap[k], heap[k / 2]);
        k /= 2;
    }
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    idx = n;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", heap + i);
    }
    for (int i = n / 2; i; i--) {
        down(i);
    }
    for (int i = 0; i < m; ++i) {
        printf("%d ", heap[1]);
        heap[1] = heap[idx];
        idx--;
        down(1);
    }
    return 0;
}