数据结构 THU 2018 - 堆

2024-02-01 23:53:04

二叉堆（Binary Heap）没什么神秘，性质比二叉搜索树 BST 还简单。其主要操作就两个，sink（下沉）和 swim（上浮），用以维护二叉堆的性质。

其主要应用有两个，首先是一种排序方法**「堆排序」，第二是一种很有用的数据结构「优先级队列」**。

本文就以实现优先级队列（Priority Queue）为例，通过图片和人类的语言来描述一下二叉堆怎么运作的。

一、二叉堆概览

首先，二叉堆和二叉树有啥关系呢，为什么人们总数把二叉堆画成一棵二叉树？

因为，二叉堆其实就是一种特殊的二叉树（完全二叉树），只不过存储在数组里。一般的二叉树，我们操作节点的指针，而在数组里，我们把数组索引作为指针：

// 父节点的索引
int parent(int root) {
    return root / 2;
}
// 左孩子的索引
int left(int root) {
    return root * 2;
}
// 右孩子的索引
int right(int root) {
    return root * 2 + 1;
}

画个图你立即就能理解了，注意数组的第一个索引 0 空着不用，

你看到了，把 arr[1] 作为整棵树的根的话，每个节点的父节点和左右孩子的索引都可以通过简单的运算得到，这就是二叉堆设计的一个巧妙之处。为了方便讲解，下面都会画的图都是二叉树结构，相信你能把树和数组对应起来。

二叉堆还分为最大堆和最小堆。最大堆的性质是：每个节点都大于等于它的两个子节点。 类似的，最小堆的性质是：每个节点都小于等于它的子节点。

两种堆核心思路都是一样的，本文以最大堆为例讲解。

对于一个最大堆，根据其性质，显然堆顶，也就是 arr[1] 一定是所有元素中最大的元素。

二、优先级队列概览

2.1 优先级队列的概念

优先级队列这种数据结构有一个很有用的功能，你插入或者删除元素的时候，元素会自动把最大（或者最小）的元素排到队首，这底层的原理就是二叉堆的操作。

数据结构的功能无非增删改查，优先级队列有两个主要 API，分别是 insert 插入一个元素和 delMax 删除最大元素（如果底层用最小堆，那么就是 delMin）。

2.2 为什么要引入优先级队列

	vector	sorted vector	list	sorted list
getmax	O(n)	O(1)	O(n)	O(1)
delmax	O(n)+O(n) = O(n)	O(1)	O(n)	O(1)
insert	O(1)	O(logn) + O(n)	O(1)	O(n)

对于AVL、Splay、Red-Black Tree, 三个接口只需要O(logn),但是BBST远远超出了优先级队列的需求…

2.3 代码框架

下面我们实现一个简化的优先级队列，先看下代码框架：

class heap {
public:
    vector<int> PQ = {-1}; //用向量来构造堆，索引0不用
    int parent(int root){
        return root/2;
    }
    int left_child(int root){
        return root*2;
    }
    int right_child(int root){
        return root*2+1;
    }
    int GetMax(){
        return PQ[1];
    }
    void insert(int val){//插入元素

    }
    int DelMax(){//删除并返回队列中的最大元素

    }
    int swim(int k){//上浮第 k 个元素，以维护最大堆性质

    }
    int sink(int k){//下沉第 k 个元素，以维护最大堆性质

    }
};

空出来的四个方法是二叉堆和优先级队列的奥妙所在，下面用图文来逐个理解。

2.3.1 swim（上浮）

上浮的原因是某些节点会违反堆序性，即有些节点比自己的父亲还要强，此时它会顶替父亲的位置。例如，在这个例子中插入了“42”：

    int swim(int k){//上浮第 k 个元素，以维护最大堆性质
        while(k>1 && PQ[k] > PQ[parent(k)]){ //尚未到根，且比自己父亲强
            swap(PQ[k],PQ[parent(k)]);
            k = parent(k);
        }
    }

2.3.2 sink

下沉比上浮略微复杂一点，因为上浮某个节点 A，只需要 A 和其父节点比较大小即可；但是下沉某个节点 A，需要 A 和其两个子节点比较大小，如果 A 不是最大的就需要调整位置，要把较大的那个子节点和 A 交换。

    int sink(int k){//下沉第 k 个元素，以维护最大堆性质
        while(left_child(k) < PQ.size()){//不是叶子节点
            int max_child = max(PQ[left_child(k)],PQ[right_child(k)]);//找到最大的孩子
            if(PQ[k] > max_child) break; //堪为父亲！
            if(max_child == PQ[left_child(k)]){//最大的是左孩子
                swap(PQ[k],PQ[left_child(k)]);
                k = left_child(k);//下沉
            }
            else {//最大的是右孩子
                swap(PQ[k], PQ[right_child(k)]);
                k = right_child(k);
            }
        }
    }

2.3.3 Delete

删除首个节点（最大的节点），并将最末的元素和根节点对换，然后不断下沉。

    int DelMax(){//删除并返回队列中的最大元素
        int max = PQ[1];
        PQ[1] = PQ[PQ.size()-1];
        PQ.pop_back();
        sink(1);
        return max;
    }

2.3.4 insert

先将词条e作为末尾元素接入向量，之后上浮之。

    void insert(int val){//插入元素
        PQ.push_back(val);
        swim(PQ.size()-1);//上浮
    }

三、最后总结

二叉堆就是一种完全二叉树，所以适合存储在数组中，而且二叉堆拥有一些特殊性质。

二叉堆的操作很简单，主要就是上浮和下沉，来维护堆的性质（堆有序），核心代码也就十行。

优先级队列是基于二叉堆实现的，主要操作是插入和删除。插入是先插到最后，然后上浮到正确位置；删除是调换位置后再删除，然后下沉到正确位置。核心代码也就十行。

参考资料：
https://github.com/labuladong/fucking-algorithm/blob/master

码农公寓