简介
堆是一种基于完全二叉树的数据结构.
完全二叉树:
- 每个节点最多有两个子节点(二叉)
- 除了最底层, 其他每一层都必须填满, 最底层也需要从左到右依次填入数据.
当一棵完全二叉树满足下列条件时即称为堆:
每个父节点都大于等于(或者小于等于)它的两个子节点.
大于等于的情况称为大根堆, 小于等于的情况称为小根堆.
本文以小根堆为例, 大根堆可以很容易类比.
如下图所示即为一个小根堆:
小根堆
堆的存储
堆的存储通过数组来实现, 由于其满足完全二叉树的性质.
则有第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以后堆结构即遭到破坏(缺失了首元素), 此时可以通过下列步骤恢复:
- 将最后一个元素放到堆顶.
- 将堆顶元素向下调整.
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要解决给出一个数组, 用这个数组构建堆的问题.
解决了堆的插入, 删除等操作的问题, 再解决堆化的问题就比较容易了.
有以下两种思路:
- 把数组里的数一个一个取出来, 插入堆中.
- 对数组里的每一个非叶子节点的数进行向下调整的操作.
以上两种思路均可以通过上述实现的调整函数进行实现.
注:思路2下, 最后一个非叶子节点的位置为n/2-1, 所以从n/2-1往回遍历即可.
堆排序
由于堆的顶部总是最小的数, 只需要每次将顶部的数取出, 然后再将堆调整为最小堆即可.
取出一个数, 最多需要调整logN次, 有N个数需要取出
所以堆排序的时间复杂度为NlogN.
