个人主页:星纭-CSDN博客
系列文章专栏 :数据结构
踏上取经路,比抵达灵山更重要!一起努力一起进步!
一.堆排序
在前一个文章的学习中,我们使用数组的物理结构构造出了逻辑结构上的堆。那么堆到底有什么用呢???
首先思考这样一个问题,假设给定一个随机的数组,如何将这个数组建堆(在不使用额外的空间的条件下)。
这个问题不难,只需用到向上调整算法即可。
int main()
{int a[] = { 4,2,8,1,5,6,9,7,3,2,23,55,232,66,222,33,7,1,66,3333,999 };int i = 1;for (i = 1; i < sizeof(a) / sizeof(a[0]); i++) {AdjustUp(a, i);}return 0;
}
通过调试不难发现此时已经是一个大堆了。
如果想要得到小堆,只需要更改向上调整函数即可。
得到了大堆之后,又如何将这个数组排序得到一个升序的数组呢???
因为在大堆中,堆顶的数据一定是最大的,可以先将堆顶数据和数组最后一个位置上的数据进行交换,不管此时最大的数据,只看前size-1这个数据,进行向下调整得到第二大的数据,再更倒数第二个位置上的数据进行交换,..........依次进行下去就会得到一个升序的数组。
int main()
{int a[] = { 4,2,8,1,5,6,9,7,3,2,23,55,232,66,222,33,7,1,66,3333,999 };int i = 1;for (i = 1; i < sizeof(a) / sizeof(a[0]); i++) {AdjustUp(a, i);}int end = sizeof(a) / sizeof(a[0]) - 1;while (end > 0) {Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}return 0;
}
简单来说,升序,建大堆,降序,建小堆。这就是堆排序。
然后就是向下调整建堆。假设给定一个数组,使用二叉树的形式表示,如下图所示
假设这个二叉树,对于根来说,其左子树是大堆,右子树也是大堆,而这整个二叉树并不是大堆,我们就可以使用向下调整来使其变成大堆。可是这样一个随机的数组肯定是不满足上述的条件的,那么该如何使用向下调整算法来使其变成大堆呢?
答案就是倒着调整。
假设我们从最后一个数据开始,一个节点是既可以看作大堆也可以看作小堆的,此时我们就不需要对其进行调整,对于完全二叉树来说,他的叶子节点都不需要调整,所以我们就需要调整倒数第一个非叶子节点。以上图举例,也就是第三层第二个节点,将它和它的孩子节点看作一个树,这样就可以调整了。
那么倒数第一个非叶子节点的下标该怎么求呢?
倒数第一个非叶子节点是最后一个节点父亲节点。而最后一个节点的下标是n-1。所以倒数第一个非叶子节点的下标就是(n-1-1)/ 2;
for (int i = (n-1-1)/2; i >= 0; i--){AdjustDown(a, n, i);}
二.建堆的时间复杂度
既然有两种不同的建堆算法,那么采用哪一种算法来建堆是更加好的呢?
所以接下来算一算两个算法的时间复杂度
对于一个完全二叉树而言,假设其高度是h,那么它的节点个数最少和最多情情况,分别是最后一层只有一个节点和一个满二叉树。
对于一个满二叉树来说总节点个数n和高度h的关系是
F(n) = 2^0 + 2^1 + 2^2 + ... + 2^(h-1) = 2^h - 1。
h = log2(n + 1)
对于最后一层只有一个节点的二叉树而言总节点个数和高度h的关系是
F(n) = 2^0 + 2^1 + 2^2 + ... + 2^(h-2) + 1 = 2^(h-1) - 1 + 1= 2^(h-1)。
h = log2(n) - 1
根据大O的渐进表示法,我们可以大致得到h = logN的。
这样我们就得到了h和N之间的关系。
1.向上调整
计算向上调整的时间复杂度,我们需要计算总共向上调整了几次。
T(h) = 2^1*1 + 2^2 * 2 + ... + 2^(h-2)*(h-2) + 2^(h-1)*(h-1).
2*T(h) = 2^2*1 + 2^3 * 2 + ... + 2^(h-1)*(h-2) + 2^h*(h-1).
-T(h) = 2^1 + 2^2 + ... +2^(h-1) - 2^h*(h-1).= 2^h - 2 -2^h*(h-1)= 2^h(1-h+1) -2 T(h) = 2 + 2 ^ h * hT(N) = 2 + 2 * log(N) * N = O(N * logN)
向上调整的时间复杂度是N*logN.
2.向下调整
T(h) = 2^0*(h-1) + 2^1*(h-2) + ... +2^(h-2) * 1
2 * T(h) = 2^1*(h-1) + 2^2*(h-2) + ... +2^(h-2) * 2+2^(h-1) * 1
T(h) = 2^1 + 2^2+...+2^(h-2) +2^(h-1) - (h-1)= 2^h - 2 - h + 1= 2^h - h - 1= N - logN - 1= O(N)
对比不难发现向下调整的时间复杂度算法更优。
三.TopK问题
TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能
数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:
1. 用数据集合中前K个元素来建堆
前k个最大的元素,则建小堆
前k个最小的元素,则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
利用此算法的时间复杂度是O(N)