丹东做网站的,网站建设和管理维护,2021年重大新闻事件,开发次元世界今天文章的内容是关于我们如何利用堆的特性对我们的数组进行排序#xff0c;还有就是我们的TopK的问题#xff0c;这次我们放在的是文件种#xff0c;我们放入一亿个数字#xff0c;然后我们取出一亿个数字中最大的十个数#xff0c;利用上章堆的问题进行解决。 首先就是我… 今天文章的内容是关于我们如何利用堆的特性对我们的数组进行排序还有就是我们的TopK的问题这次我们放在的是文件种我们放入一亿个数字然后我们取出一亿个数字中最大的十个数利用上章堆的问题进行解决。 首先就是我们如果对一个数组要进行排序这个数组是没有任何规律的就像下面的这个数组。
int arr[] { 9,4,3,19,12,13,5,8,9 };那我们得利用我们堆的特性因为我们知道堆的特性首先堆顶的数据一定是最小的那我们要进行排序之前的话要做的一个最重要的步骤就是先建立一个堆出来我们可以用两种方法一种是向上建堆另一种就是向下建堆这两个方法我们都会讲。
向上建堆 首先我们这里给的例子是升序但是在升序的时候我们是建立大堆还是小堆呢答案是大堆那我们先来看看减小堆的时候会产生怎样的问题再来看看大堆两者相互比较之后我们就会发现升序就应该建立大堆。 首先就是复用我们上次堆的内容的向上建堆的那个方法就是AdjustUp如果这里大家不明白可以回头看看我这里直接给出代码。
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
void AdjustUp(int* a, int child)
{int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}我们可以看到这是向上调整那我们建堆的过程是不是从二叉树的第二层开始往上建堆比较的就是孩子和父亲的关系那我们这里就可以写一个循环来完成这个建立堆的过程。
int arr[] { 9,4,3,19,12,13,5,8,9 };for (int i 1; i sizeof(arr) / sizeof(arr[0]); i){AdjustUp(arr, i);}然后我们这个过程建立出来堆的样子就是我们的小堆 小堆建好之后我们后面一步就是进行排序但是排序有个问题虽然我们保证了一开始堆顶的元素是最下的但是我们怎么找出第二小和第三小的数如果我们这里有人说我们可以利用堆的向下调整方法然后重新建立堆找出次小的一次这样往下走就没问题虽然说这样是可以完成排序但是这样的排序方法甚至比冒泡还慢看似用了堆的特性其实时间复杂度比冒泡排序还高那这样就没能完成我们堆的作用但是如果我们建立大堆的话结果·就·有所·不一样我们可以不找小的我们先排序后面的。 建立大堆后的样子那我们可以先交换第一个元素和最后一个元素然后再进行 向下调整我们后面也会详细计算向下调整和向上调整的时间复杂度的我们先来看如果交换第一个和最后一个元素的位置那就变成下面这样。 这是进行交换之后的样子但是还是有问题我们要保证我们这个还是大堆那该怎么做呢首先就是得向下调整向下调整就是堆顶的元素往下调整我们利用堆的特性之间写的AdjustDown调整好之后是下面的这个图。 这个时候我们发现最后一个元素是最大的有序的而且我们还是大堆那现在堆顶的元素就是次·大的数所以现在要做的就是第一个和倒数第二个换位置然后再进行调整这样倒数两个的就是有序有序之后他还是大堆堆顶的元素就是第三个最大的数这样一次循环一直到最后就变成有序了。 那我们的代码就是下面这个其实代码很简答的主要可能难理解。 AdjustDownvoid AdjustDown(int* a, int size, int parent)
{int child 2 * parent 1;while (child size){if (a[child 1] a[child] child1 size){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child 2 * parent 1;}else{break;}}
}这个就是AdjustDown的代码再堆里讲过这样就不将了来看我们如何进行排序的部分代码
int end n - 1;while (end 0){Swap(arr[0], arr[end]);AdjustDown(arr, end, 0);//这里的end是元素个数如果是下标的话就是指最后一个元素的后一个end--;}end 0的时候就说明已经排序好了所以这个就是判断条件然后来看我们的end一开始就是指向最后一个元素因为是数组所以这里表示的就是下标我们这里就是要注意这个然后先是交换堆顶元素和最后一个元素的问题就直接开始调整但是调整的时候我们end并没有进行–因为AdjustDown的size位置的参数表示的就是元素个素然后我们调整的时候因为最后一个元素已经有序了所以就不用在进行调整了。 我们来看看结果 可以发现我们也是排好序了这里呢还有要讲一个内容就是建堆我们那个时候建堆是向上调整是从第二层开始的我们也可以用向下建堆的方法向下建堆要保证两边的子树都是堆比如我们现在是大堆所以子数就得是大堆我们第一次进行调整得应该是第一个父亲节点我们可以用size - 1- 1/ 2找到第一个父亲节点。因为我们堆虽然看起来是个二叉树但是实际上就是一个数组我们这里来看代码是如何实现得。
int main()
{int arr[] { 9,4,3,19,12,13,5,8,9 };int n sizeof(arr) / sizeof(arr[0]);for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(arr, n, i);}for (int i 0; i sizeof(arr) / sizeof(arr[0]); i){printf(%d , arr[i]);}printf(\n);int end n - 1;while (end 0){Swap(arr[0], arr[end]);AdjustDown(arr, end, 0);//这里的end是元素个数如果是下标的话就是指最后一个元素的后一个end--;}for (int i 0; i sizeof(arr) / sizeof(arr[0]); i){printf(%d , arr[i]);}return 0;
}这个就是只用了向下调整进行排序建堆得方法也是用的向下调整得这个方法那我们后面得来计算一下向上调整和向下调整得时间复杂度这里先给出得结论就是向下建堆的方法才是最高效的我们下面给出一个图来分别计算出他们的时间复杂度。 我们给出这样的一个图首先就是假设这颗数的高度就是H然后我们在旁边写出他们每一层的节点数。 那我们可以再来计算一下他们如果是向上调整的话需要进行的调整次数。 那这个时候我们只要帮他们相乘起来得到一个需要裂项相消的函数。 又因为我们的高度和我们节点个数有个等式我们就可以把h变成N表示我们来看看。 这个就是我们向上调整的方式如果是向下调整的话一样的道理只是我们是从倒数第二层开始其实大家自己试试就行了计算起来是一样的方法时间复杂度是ON我们其实也可以通过分析得出因为向上调整的方法是和向下的一样的我这里就讲一个我们不难看出向上调整的时间复杂度是高于向下的这是为什么我们可以看他们最多层向上调整的时候我们最多层是最后一层他的节点数最多高度也是最高的所以是多对多时间复杂度就是要比我们的向下调整我们向下调整时从最后面的父亲节点开始的而且只要调整一次就行了这就是多对少倒数第二层的节点基本上是整个节点的最后一个所以我们这里得出的结论就是向下调整是最快的。我们后面就可以直接只用一个向下建堆就可以解决问题了。其实我们这里的排序本质上还是选择排序。 这个是向下建立堆的计算过程大家可以看看实在不会就私信小编谢谢大家。
还有一个TopK问题放在下一篇文章里因为这样流量多哈哈哈哈哈下篇文章见。
