二叉堆

定义

二叉堆是一种完全二叉树，用于维护动态序列最值。

分类

• 大顶堆：父节点 $\geq$ 子节点，维护最大值
• 小顶堆：父节点 $\leq$ 子节点，维护最小值

本篇笔记以大顶堆为例

存储

二叉树顺序存储法

• 父节点：$\frac{i}{2}$
• 左子树：$i \times 2$
• 右子树：$i \times 2 + 1$

基本操作

上浮

从某个元素开始向上比较，维护堆序性

步骤

• 比较元素与父节点
• 如果元素 $\gt$ 父节点，则交换
• 继续和当前父节点比较
• 重复上述步骤，直到元素 $\leq$ 父节点

代码

void pushup(int i){
    // 不是根节点，且元素 > 父节点
    while(i > 1 && heap[i] > heap[i/2]){
        // 交换元素与父节点
        swap(heap[i], heap[i/2]);
        // 继续向上
        i /= 2;
    }
}

下沉

从某个元素开始向下比较，维护堆序性

步骤

• 比较节点与左右子节点中较大的
• 如果元素 $\lt$ 该子节点，则交换
• 继续和当前子节点比较
• 重复上述步骤，直到元素 $\geq$ 左右子节点

代码

void pushdown(int i){
    // 左子树存在
    while(i * 2 < heap.size()){
        // 先取左子树
        int son = i * 2;
        // 右子树存在
        if(son + 1 < heap.size())
            // 取较大的子节点 
            if(heap[son+1] > heap[son]) son++;
        // 如果当前节点 < 子节点
        if(heap[i] < heap[son]){
            // 交换元素与子节点
            swap(heap[i], heap[son]);
            // 继续向下
            i = son;
        }
        // 满足堆序性，退出
        else break;
    }
}

应用操作

入堆

• 插入元素到末尾
• 元素上浮

void push(int x){
    // 插入元素到末尾
    heap.push_back(x);
    // 上浮
    pushup(heap.size() - 1);
}

出堆

• 把末位元素放到堆顶
• 删除多余末尾
• 堆顶下沉

void pop(){
    // 末位元素放到堆顶
    heap[1] = heap.back();
    // 删除多余末尾
    heap.pop_back();
    // 下沉
    pushdown(1);
}

获取堆顶

• 直接返回堆顶元素

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

建堆

逐个插入法

• 依次插入元素

void build(vector<int> &nums){
    for(int i: nums) push(i);
}

自底下沉法

• 从最后一个非叶子节点开始
• 逐个元素下沉

越靠下的节点下沉时步骤越少，而二叉堆大多数节点都在下方，所以逐个元素下沉效率更高

void build(vector<int> &nums){
    heap = vector<int>(nums);
    // 从最后一个非叶子节点开始
    for(int i = nums.size() / 2; i > 0; i--){
        // 逐个元素下沉
        pushdown(i);
    }
}

复杂度

时间复杂度

• 上浮：$O(\log n)$
• 下沉：$O(\log n)$
• 入堆：$O(\log n)$
• 出堆：$O(\log n)$
• 建堆
  • 逐个插入法：$O(n \log n)$
  • 自底上浮法：$O(n)$
• 获取堆顶：$O(1)$

空间复杂度

• 二叉堆：$O(n)$

应用

堆排序

给无序序列排序

• 建堆
• 一次取出

Top K问题

求序列的前k大/小元素

• 维护大小为k的堆
• 每次与堆顶比较，合法则替换
• 最后堆顶是第k大/小元素，堆内是前k大/小元素

多路归并

合并k个有序序列

• 维护大小为k的堆
• 每次取出堆顶，将该元素加入结果序列
• 将堆顶元素所处序列的下一个元素加入堆

对顶堆

求序列的中位数

• 维护序列左右半边两个堆
• 保持两个堆大小平衡
• 当序列长度为奇数时，返回左堆顶
• 当序列长度为偶数时，返回两个堆顶平均值

延迟删除

• 另开一个map，记录堆中需要删除的元素
• 堆顶在map中存在时，删除堆顶