一、前言
堆排序与Top K问题是堆的两大应用,在我们日常也有很广泛的用处
我们已经上面已经说过了堆,这次来说堆的其中一个应用---堆排序。
二、堆排序
堆排序优势在哪里?有什么恐怖之处吗?
重点:拿一个举例:我们上一篇博客在代码运用过程中,我们的HeapPop函数每次删除堆顶元素之后进行向下调整之后,都能找到次大或者次小的值。
int main()
{HP php;InitHeap(&php);int a[] = { 4,7,2,3,9,5,1 };for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)//建堆{PushHeap(&php, a[i]);}while (!HeapEmpty(&php))//进入循环,直至堆为空{printf("%d ", HeapTop(&php));//打印堆顶元素HeapPop(&php);//删除堆顶元素}DestroyHeap(&php);return 0;
}
这样就把我们所想要的排序好了,我们每取出一个次大或者次小的值,时间复杂度都是O(log N),当有1000个数据时,各个元素比较查找那就需要进行1000次,而我们这种做法10次就够了。效率很高。分析上面代码,还是有点缺陷的,在我们建堆的时候,我们是从源头数组里面取数据,再新开辟空间建堆,源头数组并没有变化,这便造成了空间的浪费。所以,有没有一种高效又节省空间的方法呢----堆排序。
我们要想节省空间,最好需要做到不另开辟空间,我们已经定义了一个数组,并且想将数组里面的元素进行排序,那为什么我们不在原数组上找路子呢?
1、建堆
开辟空间的建堆方式,先将源头数组里面的元素放入我们开辟的结构体中的数组里,再进行向上调整建堆。那为何我们不直接将源头数组元素直接进行向上调整呢?
我们可以直接将原数组传给AdjustUp函数,再先将数组中第一个元素进行向上调整,接着再第二个元素,这样依次进行向上调整。
int a[] = { 4,7,2,3,9,5,1,6,8};int n = sizeof(a) / sizeof(a[0]);int i = 0;for (i = 1; i < n; i++){AdjustUp(&a, i);}
我们打印一下看看结果:
因为我们上述向上调整函数最终调整为小堆,这里就拿小堆来做参考:
监视查看数组的变化:
可以看到,数组中元素已经是小堆。这样既满足了我们的建堆要求,也降低了空间的消耗
2、排序
那么,话说回来,堆是随便建的吗?直接建一个大堆或者小堆都可以满足我们要求吗?有没有什么要求呢?
我们在开头举国一个例子:我们的HeapPop函数每次删除堆顶元素之后进行向下调整之后,都能找到次大或者次小的值。
HeapPop函数的逻辑是,将堆顶元素A与堆尾元素B互换,然后A删除,将B向下调整建堆。
如果刚开始建的是小堆,我们交换堆顶元素A和队尾元素B后不着急删除A,既然是小堆,那么A肯定是所有元素中的最小值,交换后在队尾。我们再进行向下调整后,重建建小堆(这里重新建堆时不要将A也加入建堆的操作中,因为我们没有删除A),这时候的堆顶元素就是次小的值。我们将堆顶元素再与倒数第二个元素进行交换,这样次小的值就在倒数第二个位置了,再进行向下调整。这两个操作多次进行,直到剩下最后一个元素。我们每次都是找次小的值将它放在数组中最后一个,这样下来,我们最终就会得到排序好的元素,为降序。
如果是大堆呢?每次向下调整都会找到次大的值,堆顶元素与堆尾元素交换后,次大的值依次从后向前排列,最后我们便得到排序好的元素,为升序。
所以我们可以总结出,升序建大堆,降序建小堆。
代码如下(以降序举例):
int main()
{int a[] = { 4,7,2,3,9,5,1,6,8};int n = sizeof(a) / sizeof(a[0]);int i = 0;//在数组里建堆,减少了空间消耗//升序建大堆,降序建小堆 for (i = 1; i < n; i++){AdjustUp(&a, i);}//查看建堆后的元素排列for (i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");//重新定义一个变量,将元素大小赋值给它.不改变nint end = n - 1;while(end > 0){Swap_HP(&a[0],&a[end]);//交换堆顶元素与堆尾元素AdjustDown(&a,end, 0);//向下调整找到此小值end--;//在下一次交换中,让新的堆顶元素与新的堆尾元素交换。}for (i = 0; i < n; i++){ printf("%d ", a[i]);}return 0;
}
这一趟下来时间复杂度只有N*logN,比最开始学的冒泡排序快了不少。数据越多,就越能体现出堆排序的优越性!
以上就是堆排序要说的所有内容。