堆（Heap）与优先队列

堆的概念

• 一种基于完全二叉树的结构

• 大顶堆和小顶堆：
  • 大顶堆：任意的三元组，父节点都大于两个子节点。
  • 小顶堆：任意的三元组，父节点都小于两个子节点。
  • 根节点为最大值或最小值。

• 堆适合维护集合的最值

堆的基本操作（以大顶堆为例）

• 尾部插入
  • 比父节点大就和父节点交换 递归向上调整
  • 这个过程称为SHIFT-UP
• 头部弹出
  • 用最后一个元素（叶子结点）补位 递归向下调整
  • 这个过程称为SHIFT-DOWN

// 大顶堆代码实现

#define MAX_N 1000
int data[MAX_N + 5], cnt = 0;

void shift_up(int ind) {
    // 从二叉树的子节点坐标找到其父节点坐标：(ind - 1) / 2
    while (ind && data[(ind - 1) / 2] < data[ind]) {
        swap(data[ind], data[(ind - 1) / 2]);
        ind = (ind - 1) / 2;
    }
    return;
}

void shift_down(int ind) {
    // n：最大子节点坐标
    int n  = cnt - 1;
    // ind一定有子节点时
    while (ind * 2 + 1 <= n)
    {
        int temp = ind; // temp: 指向三元组中最大值的下标
        // 和左子节点比较: 小于左子节点
        if (data[temp] < data[ind * 2 + 1]) temp = ind * 2 + 1;
        // 和右子节点比较: 存在右子节点 && 小于右子节点
        if (ind * 2 + 2 <= n && data[temp] < data[ind * 2 + 2]) temp = ind * 2 + 2;
        // 判断ind是否是当前三元组中的最大值: 结束循环
        if (temp === ind) break;
        swap(data[ind], data[temp]);
        ind = temp;
    }
    return;
}

void push(int x) {
    data[cnt++] = x;
    // 尾部元素上升：新插入的最后一位元素 与其父节点比较 递归上升
    shift_up(cnt - 1);
    return;
}

void pop() {
    if (size() === 0) return; 
    // 交换头部元素和尾部元素
    swap(data[0], data[cnt - 1]);
    // 将数组范围 减去最后一位元素
    cnt -= 1;
    // 头部元素下降
    shift_down(0);
    return;
}

int top() {
    return data[0];
}

int size() {
    return cnt;
}