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

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

每个节点最多有两个子节点(二叉)

除了最底层, 其他每一层都必须填满, 最底层也需要从左到右依次填入数据.

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

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

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

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

文章图片
数组存储插入堆给出一个数组存储的堆, 如果加入了新元素, 必须想办法保持堆的特性:
完全二叉和父节点小于等于其子节点
【[数据结构]堆原理及其C++实现】加入新元素后, 只需要不断与其父节点进行比较, 根据大小关系进行调整.
即分为两步:

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

文章图片
调整

文章图片
调整后 C++实现(代码可直接运行查看结果)

#include #includeusing namespace std; void fix_up(vector & 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 & vec, int val) { vec.push_back(val); // 1.放到尾部 fix_up(vec); // 2.向上调整 }int main() { vector 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 #includeusing namespace std; void fix_down(vector & 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 & vec) { cout << "pop " << vec[0] << endl; vec[0] = vec[vec.size() - 1]; // 1. 把尾部的值放到头部 vec.pop_back(); fix_down(vec); // 2. 向下调整 }int main() { vector 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.