[数据结构]堆原理及其C++实现

简介

堆是一种基于完全二叉树的数据结构.
完全二叉树:

1. 每个节点最多有两个子节点(二叉)
2. 除了最底层, 其他每一层都必须填满, 最底层也需要从左到右依次填入数据.

当一棵完全二叉树满足下列条件时即称为堆:

每个父节点都大于等于(或者小于等于)它的两个子节点.

大于等于的情况称为大根堆, 小于等于的情况称为小根堆.
本文以小根堆为例, 大根堆可以很容易类比.
如下图所示即为一个小根堆:

小根堆

堆的存储

堆的存储通过数组来实现, 由于其满足完全二叉树的性质.
则有第i个节点(i从0开始算)的
父节点: (i-1)/2 // 为负数时则说明父节点不存在
左右子节点: (i*2+1) 和 (i*2+2)

数组存储

插入堆

给出一个数组存储的堆, 如果加入了新元素, 必须想办法保持堆的特性:
完全二叉 和 父节点小于等于其子节点

加入新元素后, 只需要不断与其父节点进行比较, 根据大小关系进行调整.
即分为两步:

1.将新的数放入数组尾部.
2.将最后一个数向上调整.

调整 调整后

C++实现(代码可直接运行查看结果)

#include<iostream>
#include<vector>

using namespace std;

void fix_up(vector <int>& vec)
{
    int pos = vec.size() - 1;
    int n_val = vec[pos];
    int parent = (pos - 1) / 2;

    while (parent >= 0 && n_val < vec[parent]){  // 有父母 且 值小于父母
        swap(vec[parent], vec[pos]);
        pos = parent;
        parent = (pos - 1) / 2;
        n_val = vec[pos];
    }
}

void heap_insert(vector <int>& vec, int val)
{
    vec.push_back(val); // 1.放到尾部
    fix_up(vec); // 2.向上调整
}

int main()
{
    vector <int> vec = { 1,4,8,7,30,10,15 };

    heap_insert(vec, 3);

    for (auto it : vec) {
        cout << it << " ";
    }

    return 0;
}

从堆中删除

堆结构仅支持从堆顶进行POP操作, 每次都能够POP出最小的元素.
POP以后堆结构即遭到破坏(缺失了首元素), 此时可以通过下列步骤恢复:

1. 将最后一个元素放到堆顶.
2. 将堆顶元素向下调整.

C++实现(代码可直接运行查看结果)

#include<iostream>
#include<vector>

using namespace std;

void fix_down(vector <int>& vec){
    if (vec.empty())
        return;
    
    int pos = 0;
    int n_val = vec[pos];
    int left = pos * 2 + 1;
    int right = left + 1;

    while (left < vec.size()){
        int *ref;
        int npos;
        if (right < vec.size()) {
            ref = &(vec[left] < vec[right] ? vec[left] :  vec[right]) ; // 跟子节点中较小节点比较.
            npos = vec[left] < vec[right] ? left : right; //下一步的位置
        }
        else {
            ref = &vec[left];
            npos = left;
        }
        if (n_val > *ref) {
            swap(vec[pos], *ref);
        }
        else
            break;
        
        pos = npos;
        left = pos * 2 + 1;
        right = left + 1;
        if(pos < vec.size())
            n_val = vec[pos];
    }
}

void pop(vector <int>& vec)
{
    cout << "pop " << vec[0] << endl;
    vec[0] = vec[vec.size() - 1]; // 1. 把尾部的值放到头部
    vec.pop_back();
    fix_down(vec); // 2. 向下调整
}

int main()
{
    vector <int> vec = { 1,4,8,7,30,10,15 };

    while (!vec.empty()){
        pop(vec);
    }

    return 0;
}

数组堆化

这一part要解决给出一个数组, 用这个数组构建堆的问题.
解决了堆的插入, 删除等操作的问题, 再解决堆化的问题就比较容易了.
有以下两种思路:

1. 把数组里的数一个一个取出来, 插入堆中.
2. 对数组里的每一个非叶子节点的数进行向下调整的操作.

以上两种思路均可以通过上述实现的调整函数进行实现.
注:思路2下, 最后一个非叶子节点的位置为n/2-1, 所以从n/2-1往回遍历即可.

堆排序

由于堆的顶部总是最小的数, 只需要每次将顶部的数取出, 然后再将堆调整为最小堆即可.
取出一个数, 最多需要调整logN次, 有N个数需要取出
所以堆排序的时间复杂度为NlogN.