堆的删除：
堆的删除操作就是删除 根节点 也就是最大或者最小的数 那大家觉得怎样删除既能删掉数据还不会破坏我们的堆结构呢？
可能我们会觉得删除数据嘛 就把它删了不就行了 把它后面的数据往前面覆盖 把它覆盖掉不就行了嘛 真的是这样嘛我们来看一下：
其次还有一个问题 就是如果这样删除数据 每次移动数据都是O(N)
现在我们再来看正确的做法：
先将最后一个数据和根节点交换然后把size--删掉最后一个数据
这样现在我们的根节点就是一个较大的数 然后使用 向下调整 函数
向下调整函数：
因为我们向下调整最多调整高度次 所以我们这个删除函数的时间复杂度是O(N)
大家看这张图明白是怎么做的了嘛
- 找出左右孩子中最小的那一个
- 与父亲比较
- 如果交换继续向下调整
两个孩子节点为什么要选最小的？
因为我们的父亲节点有两个孩子节点 要从中选出较小的那一个 该怎么选呢？
因为我们选择最小的换上去后 也是比它的兄弟节点小的
void Adjustdown(HPDataType* a, size_t size, int root)//向下调整 { size_t parent = root; size_t child = parent * 2 + 1; while (child < size) { if (child + 1 < size && a[child + 1] < a[child]) { child++; } if (a[child] < a[parent]) { swap(&a[child], &a[parent]); parent = child; child= parent * 2 + 1; } else { break; } } }
这里我们的循环条件是 while(child<n) 因为当我们排到叶子节点的时候 这个时候已经是最后一次了 之所以不用 while(parent<n) 是因为有可能这样 我们的child会越界 当 我们已经计算出child>n了 可是parent<n 这个时候在进去比较就会越界了 除非在第二个 if 判断语句那里在加一个限制条件
至于选左右孩子最小 就像上面那样就好了 但是要注意有时我们的左孩子可能不存在所以我们还要保证 child+1<n
我们的child赋值一开始也是右孩子的下标
了解了这些我们就可以实现一下我们的堆排序了
Heap hp; HeapInit(&hp); int a[11]={1,0,2,8,5,6,9,3,8,4}; for(int i=0;i<sizeof(a)/sizeof(int);i++) { HeapPush(&hp,a[i]); } size_t j=0; while(!HeapEmpty(&hp)) { a[j++]=HeapTop(&hp);//0 1 2 3 4 5 6 8 8 9 HeapPop(&hp); } HeapDestory(&hp);
大家注意我们这里的时间复杂度是 N*logN 哦 入数据是N*logN 排序也是N*logN 所以总的时间复杂度就是N*logN 因为我们有N个数 每个数无论是入数据还是删除数据每次都是logN
logN其实就是我们的层数(可以说是接近吧 毕竟2^h-1=N h=log(N+1)) 大家可以这样理解
接下来给大家说一下 另一种更好的排序 在此之前呢我们先来了解一下两种思想：向上建堆 和 向下建堆
向上建堆：
首先向上建堆的思想是 我们把一个数组的首元素看作是一个堆 其后的数据作为要插入的数据 就好像是上面堆的插入的思想
int a[10]={0}; for(int i=0;i<10;i++) { a[i]=i; } for(int i=1;i<size;i++) { AdjustUp(a,i); }
我们依次对数组中的元素进行向上调整 那么最后调整完 就是一个调整好的堆了
向下建堆：
向下建堆其实也是和向上建堆的思想其实是一样的 所以向下建堆就是使用向下调整函数来调整我们的原数组
那我们向下调整是从那里开始呢
大家看这张图觉得我们向下调整应该从那里开始呢？
如果我们从第一个数开始调 这样大家调完就会发现是不可行的 回顾我们上面的向下调整会发现我们从第一个数看它的左右子树都是小堆 所以呢 其实我们使用向下调整算法要知道开始位置往下的左右子树 要么全是大堆 要么全是小堆
看了上面这段话 大家有思路了嘛 我们知道我们在对一个节点开始向下调整 那么它的左右子树必须是堆 所以我们从下往上依次进行向下调整 那这样是不是就保证了刚刚的条件了呢
大家看这张图明白怎么做了嘛？
1. for(int i=(size-1-1)/2;i>=0;i--)//size-1是最后一个节点的下标 2. { 3. AdjustDown(a,size，i); 4. }
其实就是从 倒数的第一个非叶子节点(最后一个节点的父亲节点)开始往上递归做向下调整
我们找到后 在从该节点-- 就可以把所有的数都调整一遍了
并且建堆的方式不同 建出来的堆也是不一样的 虽然 建的都是小堆
既然有这两种方法那哪一种方法更好呢？看这文章就知道了：【数据结构】堆的建立 (时间复杂度计算-堆排序)---超细致_luck++的博客-CSDN博客
这里面还包括了 堆排序的实现 以及整体的思路 打击有兴趣可以看看哦
TopK问题：
TopK问题 字如其名 其实就是 我们在N个数里面 找出最大的（最小）前K个数
大家有什么思路嘛？
其实有这样的几个思路：
① 我们直接进行排序 选数
② 我们建立以个N个数的大堆 Pop k 次 就选出 前K个最大的数
这两种方法可行 但是万一我们的N很大呢 是不是我们的排序效率就很低了呢 是不是我们的建N个数的大堆也就空间不支持了呢？
对于这种问题我们可以这样解决：
假设我们要选前K个最大的数 我们首先排出K个数的小堆 然后我们再遍历N-K个数 如果遇到比小堆的根节点的数更大的数就交换 并且交换完对堆进行向下调整 这样就能保证下一次入数据不会因为根节点的数据更大而进不去了
void PrintTopK(int* a, int n, int k) { int* kminHeap = (int*)malloc(4 * k); assert(kminHeap); for (int i = 0; i < k; i++)//将数据放入我们建堆的数组中 { kminHeap[i] = a[i]; } for (int i = (k - 1 - 1) / 2; i >= 0; i--)//向下调整建堆（小堆） { Adjustdown(kminHeap, k, i); } for (int i = 0; i < n; i++)//N-K个数依次与堆顶的数比较 { if (kminHeap[0] < a[i]) { kminHeap[0] = a[i]; Adjustdown(kminHeap, k, 0); } } for (int i = 0; i < k; i++) { printf("%d ", kminHeap[i]); } } void TestTopk() { int* p = (int*)malloc(10000 * sizeof(int)); assert(p); srand((unsigned int)time(0)); for (int i = 0; i < 10000; i++) { p[i] = rand() % 10000; } p[1221] = 10000 + 3; p[223] = 10000 + 5; p[678] = 10000 + 9; p[345] = 10000 + 2; p[897] = 10000; p[4567] = 10000 + 10; p[2345] = 10000 + 6; PrintTopK(p, 10000, 7); }
这里我们N个数都是比10000小的数 我们随机挑选几个把它置为比10000大的数 来测试
无论我们放的数在哪都可以 大家可以下来试试
我们这种思路的时间复杂度：O(K+logK*(N-K)) 我们建堆使用的是向下建堆 时间复杂度为：O(N) 我们每次排小堆 都是logK次 最坏情况下 N-K 个数就要排
咋们这样的时间效率是不是就有了提升 相对之前的方法
到这里呢 我们关于堆的讲解就结束了 感谢大家能够看到这里！！！预祝大家都能收到自己心仪大厂的offer！！！
