上次通过数组实现堆排序的时间复杂度为O(NlogN),空间复杂度为O(N)。

优化后时间复杂度O(NlogN),空间复杂度O(1).

考虑优化方案:

1.向下调整建堆。

2.向上调整建堆。

建堆只是为了找到堆中最大或者最小的元素。

1.向上调整建堆

使用向上调整,插入数据的思想建堆。

优化方案本质上就是不开辟新的空间在原数组上进行处理,使其空间复杂度变为O(1)。
void HeapSort2(int* a,int n) { for (int i = 1; i < n; i++) { AdjustUp(a, i); }
for(int i= 0;i<n;i++) printf("%d ", a[i]); printf("\n"); }
现在对其时间复杂度进行计算,为方便计算,采用满二叉树来计算。

以下考虑的是最坏的境况:

第二层: 2^1 个结点 ,向上调整1层;

第三层: 2^2 个结点 ,向上移动2层;

……

第h层:2^(h-1)个结点,向上移动h-1层。

则需要移动的结点的次数:

T (n) = 2^1 * 1+ 2^2*2 +…+ 2^(h-1)*(h-1)

根据数列错位相减法求和公式可知

T(n) = (N+1) * ( log(N+1) - 2 )+2 当n->无穷大  T(n) = NlogN

向上建堆的时间复杂度为O(N*logN).

2.向下调整建堆

前提要求:对必须是大堆或者小堆。

所以要先对数组进行调整。

从倒数第一个非叶子结点开始(最后一个结点的父亲结点)。

因为叶子结点可以单独看作大堆或者小堆。

画图:

调整次数:4次

代码:
void HeapSort3(int* a, int n) { for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
AdjustDown(a, n, i); } for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n"); }
空间复杂度:O(1),时间复杂度O(N)

现证明时间复杂度:

第一层:2^0个结点,需要向下移动h-1层。

第二层:2^1个结点,需要向下移动h-2层。

第三层:2^2个结点,需要向下调整h-3层。

……

第h-1层,2^(h-2)个结点,需要向下移动1层。

所以移动的总次数:

T(n) = 2^0 *(h-1) + 2^1 *(h-2) + …+ 2^(h-2)* 1

根据错位相减法可得出:

T(n) = 2^h - 1 - h

又 n = 2^h - 1

T(n) = n - log(n+1) 

当n无穷大时,近似认为T(n) = n

证明完毕。

既然已经有向上建堆和向下建堆两种方法,那么哪种情况更是配建小队,哪种更适合见大堆??

升序 -- 建大堆

理由:若是升序建小堆最小的数已经在第一个位置了,剩下的关系全都乱了,需要重新建堆,建堆要O(N),再选出次小的,不断建堆选数,如此以时间复杂度O(N)的情况还不如直接遍历轻松。

总之,升序建小堆,效率低,还复杂。

降序--建小堆

那如何建大堆完成排序呢?

建大堆本质上就是尽可能维持堆的稳定。

找到最大的数后,将根位置的数与最后一个数相交换,在n-1组数据中进行向下调整,找到次小的数,将根与第n-1位置的数交换,以此实现升序。

相关代码:
void HeapSort4(int* a, int n) { for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
//建大堆 AdjustDown(a, n, i); } //找到最后一个数的下标 int end = n - 1; while (end > 0) {
//交换根和最后一个位置的值 Swap(&a[0], &a[end]); AdjustDown(a, end, 0); end--; } for (int i
= 0; i < n; i++) printf("%d ", a[i]); printf("\n"); }
Top - k 问题

求数据结合中前k个最大元素或者最小的元素,一般情况下数据量都比较大。

Top-k中最简单的方法就是排序,如果数据量非常大,排序就会出现问题(数据不能一次性加载到内存中),但是堆排序可以解决。

1.用数组中前看个元素来建堆。

求最大建小堆,求最小则建大堆。

与升序建大堆,降序建小堆原理相似。

2.用剩余的n-k个元素与对顶的元素作比较,来替换对顶的元素。

记得向下调整。
void TopK(int* a,int n,int k) { //建小堆 int* topk = (int*)malloc(sizeof(int) *
k); assert(topk); for (int i = 0; i < k; i++) { topk[i] = a[i]; } //向下调整建堆 for
(int i = (k - 1 - 1) / 2; i >= 0; i--) { AdjustDown(topk, k, i); } for (int j =
k; j < n; j++) { if (topk[0] < a[j]) { topk[0] = a[j]; AdjustDown(topk, k, 0);
} } for (int i = 0; i < k; i++) { printf("%d ", topk[i]); } printf("\n");
free(topk); } int main() { int n = 10000; int* a = (int*)malloc(sizeof(int) *
n); assert(a); srand(time(0)); for (int i = 0; i < n; i++) { a[i] = rand() %
10000; } a[0] = 100001; a[101] = 100002; a[159] = 123456; a[7459] = 100003;
a[7412] = 100009; a[7826] = 111111; a[7712] = 222222; a[9635] = 999999;
TopK(a,n,8); return 0; }

时间复杂度 O( K+ K*log(N-K) )

空间复杂度:O(K)

当K<<N时,效率也蛮高的。

有不对的地方还请大佬指出。 

技术
今日推荐
阅读数 7246
阅读数 2080
阅读数 1522
阅读数 1330
阅读数 1311
阅读数 1134
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信