二叉堆

说明

在阅读该文章的时候，最好手中有一只纸和笔能够画出二叉堆的结构，会更加容易理解。

二叉树的定义

二叉树是每个结点最多有两个子树的树结构。通常子树被称作左子树和右子树。

二叉堆的定义

当一颗二叉树的根节点都大于等于（小于等于）它的子节点时，它被称为二叉堆。 如果一个二叉堆的根节点大于等于它的所有子节点，称为最大堆。 如果一个二叉堆的根节点小于等于它的所有子节点，称为最小堆。

完全二叉树的定义

二叉堆是一颗完全二叉树即当一颗子树存在右节点的时候这颗子树一定存在左节点。我们会看到这颗二叉树的节点都是从左往右连续排列的。对于完全二叉树更加严谨的定义为：

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层所有的结点都连续集中在最左边。

二叉堆的存储

由于二叉堆是一颗完全二叉树我们可以使用一个数组来存储，数组的每个元素就是二叉堆中的各个节点。这是因为完全二叉树的节点从左至右是连续的，如果不是连续的话使用数组来存储就会浪费一些空间。 当要存储有N个节点的二叉堆时，一般会用长度为N+1的数组来存储这颗二叉堆。数组索引为1元素就是二叉堆的根节点。索引0的位置就空着不用，这是为了方便计算每颗子树的子节点和父节点的索引。

如果树的某个节点索引是k那么：

• 该节点的父亲节点索引：k/2 (向下取整)

• 该节点的左子节点索引：2k+1

• 该节点的右子节点索引： 2k+2

左子节点索引：

unsigned getLeftChildIndex(unsigned index) {
    return index * 2 + 1;
}

右子节点索引：

unsigned getRightChildIndex(unsigned index) {
    return this->getLeftChildIndex(index) + 1;
}

父节点索引：

unsigned getParentIndex(unsigned index) {
    return index / 2; // C++除法如果两边都是整型的话默认向下取整
}

二叉堆的操作

下面的操作都是以最大堆为二叉堆，即二叉堆的根节点大于等于它的所有子节点。最小堆的操作跟最大堆是一样的，只是节点间的比较不同而已。

shiftUp(上移操作)

如果一个最大堆因为一些操作使得某个节点比它的父节点还要大，此时这颗二叉树就不再满足最大堆的性质。要做的操作是把该节点与它的父节点交换位置来保证以交换位置后的该节点为根节点的这颗子树满足最大堆的性质。这个时候可能会想到如果新的根节点的另外一个子节点比这个新的根节点还要大怎么办?为什么不跟另外一个子节点也进行一次比较操作呢? 答案是因为原来的堆是满足最大堆的性质的，所以另外一个子节点一定小于等于原来的父节点，也就一定会小于新的父亲节点，所以不用进行比较。交换后新的父节点还是有可能比这个新的父节点的父节点还要大，那么就再重复一次之前的操作，这样一层一层向上移动直到堆顶或者遇到的节点不再比它的父节点大为止。整个过程就是shiftUp操作。

具体代码：

void shiftUp(unsigned index) {
    // 
    while ((index > 1) && this->container[index] >= this->container[getParentIndex(index)]) {
        swap(this->container[index], this->container[getParentIndex(index)]);
        index = index / 2;
    }
}

while中的index > 1表示该索引不是堆顶索引，this->container[index] >= this->container[index / 2]表示该节点大于它的父亲节点。只要满足这2个条件就交换位置，同时把索引设成原来节点的父节点，一样一层一层向上移动，直到不满足这2条件中的任意一个就退出。

shiftDown(下移操作)

如果一个最大堆因为一些操作使得某个节点比它的子节点还要小，此时这颗二叉树就不再满足最大堆的性质。要做的操作是把这个节点与它子节点中最大的那个节点交换位置。交换后的这个节点的位置可能还是比它的子节点小，那么就重复执行之前的操作一层一层向下移动。直到到达堆底或是遇到的节点不再比它的子节点小。该过程就是shiftDown操作。

具体代码：

void shiftDown(unsigned index = 1) {
    // 判断左子节点的索引是否超过了数组的大小,如果超过了,就代表该节点没有左子节点.
    while(this->getSize() >= getLeftChildIndex(index)) { // 如果该节点存在左子节点
        unsigned maxChildIndex = getLeftChildIndex(index); // 暂时把最大的节点设为左子节点
        if (this->getSize() >= getRightChildIndex(index)) { // 如果该节点存在右子节点
            if (this->container[getRightChildIndex(index)] > this->container[getLeftChildIndex(index)]) { // 如果右子节点比左子节点大就把最大的子节点设为右子节点.
                maxChildIndex = getRightChildIndex(index);
            }
        }
        if ((this->container[index] >= this->container[maxChildIndex])) { // 如果当前节点大于等于它最大的子节点,那么就没有打破最大堆的性质,所以直接break掉就好了.
            break;
        }
        // 如果当前节点存在一个子节点比它还要大,那么就交换这2个节点的位置,同时把当前循环的索引设为新的根节点的索引然后继续向下检查.
        swap(this->container[index], this->container[maxChildIndex]);
        index = maxChildIndex;
    }
}

该具体具体的代码实现思路就是先判断该节点是否存在左子节点，如果存在就暂时把最大的节点设为左子节点。然后判断该节点存在右子节点。如果存在的话就判断一下这2个子节点哪一个大，把大的那个设为该节点的最大子节点，再来判断一下当前节点是否大于等于这个找出来的大的子节点，如果成立就退出，因为并没有违背最大堆的性质。不成立的话就说明当前节点存在一个子节点比它还要大，那么就交换这2个节点的位置，同时把当前循环的索引设为新的根节点的索引然后继续向下检查。

取出最大值

由于最大堆的堆顶存放的是这个堆的最大值，所以从堆中取出最大值就是取出堆顶的元素。取出堆顶元素后会打破最大堆的定义，所以我们一般的操作是把堆底的元素移动到堆顶。然后再对堆顶的位置做shiftDown操作就可以恢复最大堆的定义。

具体代码：

int extractMax() {
    int root = this->container[1]; // 数组索引1的位置存放的是堆顶的元素
    int tail = this->container[this->getSize()]; // 取出堆底的元素
    // 把堆底的元素放到堆顶然后再对堆顶元素做shiftDown操作
    this->container[1] = tail;
    this->shiftDown(1);
    // 维护堆的大小
    this->size --;
    return root;
}

插入节点

往堆中插入节点的时候直接把新的节点放在堆底后一个节点的位置，然后对新的堆底的位置做shifUp操作。

具体代码：

void insert(int element) {
    // 把新的元素放在堆底后一个节点的位置
    this->container[this->getSize() + 1] = element;
    // 对新的堆底的位置做shifUp操作
    this->shiftUp(this->getSize() + 1);
    // 维护堆的大小
    this->size ++;
}

heapify

这个操作可以把一个数组构建成一个最大堆。 就是把任意一个数组通过heapify的操作，可以让其满足二叉堆的性质。

我们为了让整个二叉树都满足最大堆的性质,我们首先要保证这颗二叉树的任意一颗子树满足最大堆的性质也就是父节点大于等于它的子节点。这也体现了分而治之的思想。 所以我们要把一个数组构建成一个最大堆就需要先保证每个节点都要大于等于它的子节点。我们可以选择从数组的最后一个元素开始依次往回做shiftDown操作，这样就保证了不会有某个节点小于等于它的子节点。但是我们发现如果某个节点是一个叶子节点的话那么它根本不需要做任何操作，因为它没有子节点。所以后来优化之后我们可以从最后一个拥有子节点的节点开始往回shiftDown。最后一个拥有子节点的节点也被称为非叶子节点或是最后一个父节点它的索引就是堆底的父节点。

具体实现：

heapify(int *arr, unsigned size) {
    // size 就是堆底的位置,它的父节点就是最后一个拥有子节点的节点
    for (int i = this->getParentIndex(size); i >= 1; i --) {
        this->shiftDown(i);
    }
}

兼容最小堆和最大堆

有时候我们需要使用最小堆，但有时候我们又需要使用最大堆，但是它们两个往往代码几乎一模一样只是比较符号的不同，为了复用代码，我们只需要给二叉堆设定一个比较方法即可，比如在初始化最大堆的时候给它传入一个方法，这个方法就用来做比较操作。 当二叉堆中需要做比较的时候调用该方法即可。

如果是一个最小堆,我们的比较方法如下：

bool compare(int a, int b) {
    return a < b;
}

堆中相应地方调用的时候：

if (this->compare(this->container[getRightChildIndex(index)], this->container[getLeftChildIndex(index)])) {
// ........
}

结束语

该文章对堆的性质和常用操作做了阐述，文中的代码使用了C++，数据结构与算法的重点在于思想和逻辑所以大家完全可以在了解了算法思想之后用自己熟悉的任意一门语言来实现。后面还会出一篇关于二叉堆应用和复杂度分析的文章。

完整的代码：https://github.com/acodercat/cpp-algorithms/blob/master/include/binary_heap.h

代码测试：https://github.com/acodercat/cpp-algorithms/blob/master/src/demo/binary_heap.cpp

仓库中的二叉堆是从索引0开始的，所以在父节点索引计算上会有不同。

该仓库还有其他算法与数据结构的相应实现