堆
2021-04-30 本文已影响0人
李伟13
结构
完全二叉树（并不是满二叉树）
底层是数组
分类
- 最大堆
每个结点的值都大于或等于其左右孩子结点的值 - 最小堆
每个结点的值都小于或等于其左右孩子结点的值
最大堆性质
父节点大于所有子节点，但是左右子节点
功能:
维护动态数据的最大最小值,可以考虑使用堆
调整堆的时间复杂度O(logk)
堆的操作(以小顶堆为例)
https://www.acwing.com/blog/content/308/
heap[++size] = x;up(size); //插入一个数
heap[1]; //求最小值
heap[1] = heap[size];size--;down(1); //删除最小值
heap[k] = heap[size];size--;down(k);up(k); //删除任意一个元素
heap[k] = x;down(k);up[k]; //修改任意一个元素
- down和up的时间复杂度为O(logn)最多交换深度h - 1次,h为n的log函数
down()
循环down
- 图1 循环down,注意是fa的左侧子节点存在,即<heapSize的时候.其实还是递归比较好理解
- 注意else的break;
- 注意nums[ minmum ] 而不是u,因为两个minmum可能因为赋值会不一样
void down(vector<int>& nums, int u, int heapSize) {
//图1 循环down,注意是fa的左侧子节点存在,即<heapSize的时候.其实还是递归比较好理解
//注意else的break;
//注意nums[ minmum ] 而不是u,因为两个minmum可能因为赋值会不一样
while (u * 2 + 1 < heapSize) {
int l = u * 2 + 1, r = u * 2 + 2, minmum = u;
if (l < heapSize && nums[l] < nums[minmum]) {
minmum = l;
}
if (r < heapSize && nums[r] < nums[minmum]) {
minmum = r;
}
if (u != minmum) {
swap(nums[u], nums[minmum]);
u = minmum;
}
else {
break;
}
}
}
图1
递归down
void down(vector<int>& nums, int u, int heapSize) {
// 递归down
int l = u * 2 + 1, r = u * 2 + 2, minmum = u;
if (l < heapSize && nums[l] < nums[minmum]) {
minmum = l;
}
if (r < heapSize && nums[r] < nums[minmum]) {
minmum = r;
}
if (u != minmum) {
swap(nums[u], nums[minmum]);
down(nums, minmum, heapSize);
}
}
up()
循环up
void up(vector<int>& nums, int u, int heapSize) {
while (u && nums[(u - 1) / 2] > nums[u]) {
swap(nums[(u - 1) / 2], nums[u]);
u = u - 1 / 2;
}
}
递归up
void up(vector<int>& nums, int u, int heapSize) {
int fa = (u - 1) / 2;
if (u != 0 && nums[fa] > nums[u]) {
swap(nums[fa], nums[u]);
up(nums, fa, heapSize);
}
}
建堆
https://www.acwing.com/activity/content/code/content/493331/
-
时间复杂度为O(n),为什么?
void buildMinHeap(vector<int>& nums, int heapSize) {
for (int i = heapSize / 2; i >= 0; --i) {
down(nums, i, heapSize);
}
}
heapify
使得数组“堆有序”
- 一定是全部有序吗？为什么
不是，无法确定子节点左右大小 -
那堆排序如何实现？
小顶堆,交换top和rear的位置,size--;down(top).这样数组从大到小排列
交换n次,每次down的时间复杂度为O(logn)时间复杂度为O(nlogn)
较小值下沉
void maxHeapify(vector<int>& a, int i, int heapsize) {
//如果是基1的,那么l = i * 2, r = i * 2 + 1
int l = i * 2 + 1, r = i * 2 + 2, largest = i;
if (l < heapSize && a[l] > a[largest]) {
largest = l;
}
if (r < heapSize && a[r] > a[largest]) {
largest = r;
}
if (largest != i) {
//交换i和字节中的最大值
swap(a[largest], a[i]);
//较小值下沉
maxHeapify(a, largest, heapSize);
}
}
buildheap
void buildMaxHeap(vector<int>& a, int heapSize) {
for (int i = heapSize / 2; i >= 0; --i) {
maxHeapify(a, i, heapSize);
}
}
- heapsize不减的话一定会多做两次heapify。（其实问题不大）
