二叉堆

摘要: 经典的二叉堆的实现，附代码模板和应用

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文我们串讲一下经典的二叉堆的原理、实现，代码模板和应用。

$1 二叉堆

原理

堆是一种支持插入key，删除堆顶key，查询key的最值的数据结构，二叉堆对是一种满足堆性质的完全二叉树。

小顶堆性质：树中任意一个节点的 key 都大于等于其父节点的权值
大顶堆性质：树中任意一个节点的 key 都小于等于其父节点的权值

• 一般不支持按key操作，例如按 key 删除，按 key 修改。但是如果真有需求的话，可以通过在内部加索引的方式实现，使得给堆提供 key 之后，对内部可以找到该 key 对应的节点(数组下标)，例如索引堆。

代码

由于二叉堆具有完全二叉树的性质，因此采用数组实现二叉树的方式实现二叉堆。

• 如果根节点为 1，则左子节点为 2i，右子节点为 2i + 1，父节点为 i/2。
• 如果根节点为 0，则左子节点为 2i + 1，右子节点为 2i + 2，父节点为 (i-1)/2。

以根节点为 1 的大顶堆为例。

数据结构设计

data 持有数据，_size 表示元素个数。

vector<int> data; // keys
int _size;

(0) 调整节点 push_up(i), push_down(i)

当进行了插入，删除，修改等操作。数组中会有某个节点发生了改变。例如插入的时候，尾部节点发生改变；删除堆头的时候，头部节点发生改变。如果是按照索引进行删除或者修改，那么数组中间会有某个节点发生改变。

发生改变后，该节点可能就不满足堆的性质了。需要将节点进行调整。如果改变发生在数组的头部，只需要向下调整，如果改变发生在数组的尾部，只需要向上调整，如果改变发生在数组的中部，向上向下均需要调整。

向上调整 push_up

void push_up(int i)
{
    if(i > _size) return;
    while(i / 2 > 0 && data[i / 2] < data[i])
    {
        swap(data[i], data[i / 2]);
        i /= 2;
    }
}

向下调整 push_down

void push_down(int i)
{
    // ori 为下传的方向
    int ori = i, left = i * 2, right = i * 2 + 1;
    if(left <= _size && data[left] > data[ori])
        ori = left;
    if(right <= _size && data[right] > data[ori])
        ori = right;
    if(ori != i)
    {
        swap(data[i], data[ori]);
        push_down(ori);
    }
}

(1) 插入 push(val)

把 val 放在数组末尾，然后向上调整，直至满足堆性质

void push(int key)
{
    if(_size + 1 >= (int)data.size())
        dilatation();
    data[++_size] = key;
    push_up(_size);
}

扩容

void dilatation()
{
    vector<int> tmp_data((_size + 1) * 2 + 1);
    tmp_data[0] = 1;
    for(int i = 1; i <= _size; ++i)
        tmp_data[i] = data[i];
    data.swap(tmp_data);
}

(2) 删除堆头 pop()

int pop()
{
    if(empty())
        return -1;
    int ans = data[1];
    data[1] = data[_size--];
    push_down(1);
    return ans;
}

(3) 查询最值 top()

int top()
{
    if(empty())
        return -1;
    return data[1];
}

(4) 按下标删除 remove(i)

数组的下标是不对外暴露的，但是如果内部有一层索引满足外面直接删 key 的需求的话，内部通过 key 查到对应的节点位置(数组下标)之后会按照下标删除节点

删除过程是将该点与数组尾部节点交换，然后调整该点(此时该点持有的是原尾部节点的 key)。

void remove(int i)
{
    if(i > _size)
        return; 
    data[i] = data[_size--];
    push_up(i);
    push_down(i);
}

(5) 建堆 build(size)

给定一个数组建堆，最直观的方式是从空堆开始依次插入一个节点。时间复杂度为 $O(N\log N)$

更好的办法是将数组视为已经建好的完全二叉树，如果想用根节点为 1 的树，可以用 $O(N)$ 的时间将数组右移一位。然后自底向上建堆。

• 自底向上枚举 i(i = size,…,2,1)，向下调整 i 这个点使得 [i..size] 这若干棵树满足堆的性质。

这种枚举的方式，树的高度是逐渐变高的，假设高度为h的子树均已完成二叉堆化，那么对于高度为h+1的子树，把其根节点或底层节点做调整，最多需要h步完成二叉堆化。总时间复杂度为 $O(N)$

void build(const vector<int>& nums)
{
    data.clear();
    int n = nums.size();
    data.assign(n + 1, 0);
    data[0] = -1;
    for(int i = 0; i < n; ++i)
        data[i + 1] = nums[i];
    _size = n;
    for(int i = n; i >= 1; --i)
        push_down(i);
}

建堆的时间复杂度推导

高度为 h (根的高度为 0)的满二叉树节点个数 $S(h) = 2^{h+1}-1$

第 h 层有 $2^{h}$ 个节点。

对于节点 i (1,2,…,N)，其高度为 h $0,1,…,\lfloor \log N\rfloor$

在高度为 h 的节点向上调整的时间复杂度为 $O(h)$，向下调整的时间复杂度为 $O(\lfloor \log N\rfloor -h)$

总的时间复杂度为 $\sum\limits_{h=0}\limits^{\lfloor \log N\rfloor}2^{h} \times (\lfloor \log N\rfloor - h)$

记 $m = \lfloor \log N\rfloor$，$ O = \sum\limits_{h=0}\limits^{m}2^{h} \times (m - h) = m \times \sum\limits_{h=0}\limits^{m}2^{h} - \sum\limits_{h=0}\limits^{m}2^{h} \times h$

记 $S = \sum\limits_{h=0}\limits^{m}2^{h} \times h$

$$S = 0 \times 2^{0} + 1 \times 2^{1} + ... + m \times 2^{m} \\ 2S = 0 \times 2^{1} + 1 \times 2^{2} + ... + m \times 2^{m+1} \\$$

错位相减

$$-S = 0 + 2^{1} + 2^{2} + ... + 2^{m} - m \times 2^{m+1} \\$$ $$S = m \times 2^{m+1} - \sum\limits_{i=1}\limits^{m}2^{i}$$

等比数列求和 $\sum\limits_{i=1}\limits^{m}2^{i} = \frac{2^{1}(1 - 2^{m})}{1 - 2} = 2^{m+1} - 2$

$$S = m \times 2^{m+1} - 2^{m+1} + 2$$

因此

$$\begin{align} O &= \sum\limits_{h=0}\limits^{m}2^{h} \times (m - h) = m \times \sum\limits_{h=0}\limits^{m}2^{h} - S \\ &= m \times (2^{m+1} - 1) - (m \times 2^{m+1} - 2^{m+1} + 2) \\ &= 2^{m+1} - m - 2 \\ &= 2N - \log N - 2 \\ \end{align}$$

总时间复杂度为 $O(N)$

完整代码和测试 C++ (模板)

将前面分散的代码片段整合到一起，形成以下最大堆的代码模板。

class MaxHeap
{
public:
    MaxHeap()
    {
        data.assign(0, -1);
        _size = 0;
    }

    void build(const vector<int>& nums)
    {
        data.clear();
        int n = nums.size();
        data.assign(n + 1, 0);
        data[0] = -1;
        for(int i = 0; i < n; ++i)
            data[i + 1] = nums[i];
        _size = n;
        for(int i = n; i >= 1; --i)
            push_down(i);
    }

    int top()
    {
        if(empty())
            return -1;
        return data[1];
    }

    int pop()
    {
        if(empty())
            return -1;
        int ans = data[1];
        data[1] = data[_size--];
        push_down(1);
        return ans;
    }

    void push(int key)
    {
        if(_size + 1 >= (int)data.size())
            dilatation();
        data[++_size] = key;
        push_up(_size);
    }

    int size()
    {
        return _size;
    }

    bool empty()
    {
        return _size == 0;
    }

private:
    vector<int> data; // keys
    int _size;

    void dilatation()
    {
        vector<int> tmp_data((_size + 1) * 2 + 1);
        tmp_data[0] = 1;
        for(int i = 1; i <= _size; ++i)
            tmp_data[i] = data[i];
        data.swap(tmp_data);
    }

    void push_up(int i)
    {
        if(i > _size) return;
        while(i / 2 > 0 && data[i / 2] < data[i])
        {
            swap(data[i], data[i / 2]);
            i /= 2;
        }
    }

    void push_down(int i)
    {
        int ori = i, left = i * 2, right = i * 2 + 1;
        if(left <= _size && data[left] > data[ori])
            ori = left;
        if(right <= _size && data[right] > data[ori])
            ori = right;
        if(ori != i)
        {
            swap(data[i], data[ori]);
            push_down(ori);
        }
    }
};

使用前面的代码模板，用堆排序算法解决 912. 排序数组 问题，代码如下：

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        MaxHeap heap;
        heap.build(nums);
        vector<int> result;
        cout << heap.size() << endl;
        while(!heap.empty())
        {
            cout << heap.top() << endl;
            result.push_back(heap.pop());
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

---

$2 数组的堆排序

数组上有各种排序算法，参考文章 数组排序。

对于堆排序，建堆和维护堆的操作都可以再输入数组上原地做。因此堆排序是数组排序中，平均时间复杂度 $O(N\log N)$ 的基础上，空间复杂度可以达到 $O(1)$ 的算法。

数组的堆排序代码

void heapsort(vector<int>& nums)
{
    if(nums.empty()) 
        return;
    int n = nums.size();
    _heapsort(nums, n);
}

void _heapsort(vector<int>& data, int size)
{
    data.push_back(0);
    int n = size;
    for(int i = n - 1; i >= 0; --i) 
        data[i + 1] = data[i]; // 堆中元素在内部数组中的下标从 1 开始
    for(int i = n; i >= 1; --i) 
        push_down(data, size, i); // 时间复杂度 O(N) 不是 O(N\log N)
    for(int i = n; i >= 1; --i)
    {
        swap(data[1], data[size--]);
        push_down(data, size, 1);
    }
    for(int i = 0; i < n; ++i) 
        data[i] = data[i + 1];
    data.pop_back();
}

数组的堆排序和快排的对比

快排和堆排同样是不稳定排序，并且时间复杂度 $O(N\log N)$ 的排序。这两个的对比就比较有意思了。

• 堆排序的时间性能略差，虽然最坏情况下堆排序可以有 $O(N\log N)$ 而快排是 $O(N^{2})$，但是当数据量不很小的时候最坏情况的概率极低，而堆排序虽然是 $O(N\log G)$ 但是常数大，所以快排在实战中往往比堆排块。
• 堆排序的空间性能略好，因为快排需要基于递归来做。

更深入的参考:

• 数学之美番外篇：快排为什么那样快
• 知无涯之std::sort源码剖析
• A Basic Comparison of Heap-Sort and Quick-Sort Algorithms

---