实现堆排序

灰太狼 2022-08-06 13:15 173阅读 0赞

**实现堆排序**

# 1. 堆排序的思想 #

堆是一棵完全二叉树，任何一个节点的val不大于（最小堆）或者不小于（最大堆）其左右孩子节点的关键字。

以最大堆为例，堆排序的基本思想是：

1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；  
  
2)将堆顶元素R\[1\]与最后一个元素R\[n\]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R\[1,2...n-1\]<=R\[n\];  
  
3)由于交换后新的堆顶R\[1\]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R\[1\]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

其实，堆排序最重要的两部分就是：初始化堆和调整堆。

我们可以用下图展示堆排序的过程：

给定一个整形数组a\[\]=\{16,7,3,20,17,8\}，对其进行堆排序。

1） 构建最大堆；

![Center][]这一步骤只需要构建一个完全二叉树即可；

2）初始化最大堆；

![Center 1][]![Center 2][]

这一步骤需要不断调整，使得堆成为最大堆。

调整从最后一个非叶子节点开始。每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整)。

3）排序，继续调整最大堆；

堆顶20和3交换：![Center 3][]![Center 4][]![Center 5][]

堆顶17和3交换：![Center 6][]

堆顶16和3交换：![Center 7][]![Center 8][]

堆顶8（7）和3交换：![Center 9][]

总的来说，堆排序就是一个不断调整堆的过程。

堆排序其实也是一种选择排序，是一种树形选择排序。只不过直接选择排序中，为了从R\[1...n\]中选择最大记录，需比较n-1次，然后从R\[1...n-2\]中选择最大记录需比较n-2次。事实上这n-2次比较中有很多已经在前面的n-1次比较中已经做过，而树形选择排序恰好利用树形的特点保存了部分前面的比较结果，因此可以减少比较次数。对于n个关键字序列，最坏情况下每个节点需比较log2(n)次，因此其最坏情况下时间复杂度为nlogn。

堆排序为不稳定排序，不适合记录较少的排序。

# 2. 编程实现堆排序 #

#include<iostream>
    #include<algorithm>
    using namespace std; 
    
    // 调整堆函数
    void HeapAdjust(int *a, int i, int size)  // a：数组；i：节点index；size：树的规模
    {
    	int lchild = 2 * i;   // 节点的左孩子编号
    	int rchild = 2 * i + 1;   // 节点的右孩子编号
    	int max = i;  //节点编号备份
    	if(i <= size/2 - 1)
    	{
    		if(lchild <= size && a[lchild] > a[max])  // 左孩子比节点值要大
    			max = lchild; 
    		if(rchild <= size && a[rchild] > a[max])  // 右孩子比节点值要大
    			max = rchild; 
    		if(max != i)  // 如果上面发生了交换，也就是如果上面有if成立了
    		{
    			swap(a[i], a[max]);   // 首先要交换二者的真实值，因为上面只是index的交换
    			HeapAdjust(a, max, size);  // 其次，需要判断交换之后还需要重新调整吗
    		}
    	}
    }
    
    //建立堆函数
    void BuildHeap(int *a, int size)  
    {
    	int i; 
    	for(i = size/2 - 1; i >= 0; i--)  // 非叶子节点最大序号值为size/2，需要遍历所有的节点
    	{
    		HeapAdjust(a, i, size);   // 调整
    	}
    }
    
    // 堆排序函数
    void HeapSort(int *a, int size)
    {
    	int i; 
    	BuildHeap(a, size); 
    	for(i = size; i >= 0; i--)
    	{
    		swap(a[0], a[i]);  //  交换堆顶和最后一个元素，每次将剩余元素中的最大者放到最后面
    		HeapAdjust(a, 0, i-1);  // 重新调整堆顶节点成为大顶堆，这个时候就要除出最后一个元素，范围是1~n-1
    	}
    }
    
    int main()
    {
    	int a[] = {100, 16, 20, 3, 11, 17, 8};
    	int size = 7; 
    	HeapSort(a, size); 
    	for(int i = 0; i < size; i++)
    	{
    		cout<<a[i]<<endl; 
    	}
    	cout<<endl; 
    
    	return 0; 
    }

参考链接：

http://www.cnblogs.com/dolphin0520/archive/2011/10/06/2199741.html

[Center]: /images/20220806/94973e46258142588ea55dd38669c1fc.png
[Center 1]: https://img-blog.csdn.net/20150127145511736?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcHVxdXRvZ2V0aGVy/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 2]: /images/20220806/ba6b56ae8a614b47be3081e55883cd32.png
[Center 3]: https://img-blog.csdn.net/20150127150026170?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcHVxdXRvZ2V0aGVy/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 4]: https://img-blog.csdn.net/20150127150011718?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcHVxdXRvZ2V0aGVy/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 5]: /images/20220806/e28f7c38d38646a1956fae86c69a20c1.png
[Center 6]: /images/20220806/3aea2b84dcaa47f98ebd888f6a0c7256.png
[Center 7]: https://img-blog.csdn.net/20150127150150410?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcHVxdXRvZ2V0aGVy/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 8]: /images/20220806/9bbd3101c574485da7679ed4c198fbd1.png
[Center 9]: /images/20220806/15d12186e7be49f096d7276d31483d89.png