【数据结构】中的堆(HeapSort)排序

男娘i 2022-06-16 11:44 234阅读 0赞

堆排序(Heapsort)是指利用堆积树（堆）这种资料结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。

其基本思想为(大顶堆)：

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，则整个排序过程完成。

操作过程如下：

1)初始化堆：将R\[1..n\]构造为堆；

2)将当前无序区的堆顶元素R\[1\]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。

因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。

堆排序中最重要的是建立大堆，使用向下调整的方法：

void AdjustDown(int *a, size_t n, int root)
    {
    	size_t parent = root;
    	size_t child = parent * 2 + 1;
    	while (child < n)
    	{
    		if (child + 1 < n && a[child + 1] > a[child])
    		{
    			++child;
    		}
    		if (a[child] > a[parent])
    		{
    			swap(a[child], a[parent]);
    			parent = child;;
    			child = parent * 2 + 1;
    		}
    		else
    		{
    			break;
    		}
    	}
    }

完整的代码如下：

#include<iostream>
    using namespace std;
    #include<assert.h>
    
    void AdjustDown(int *a, size_t n, int root)
    {
    	size_t parent = root;
    	size_t child = parent * 2 + 1;
    	while (child < n)
    	{
    		if (child + 1 < n && a[child + 1] > a[child])
    		{
    			++child;
    		}
    		if (a[child] > a[parent])
    		{
    			swap(a[child], a[parent]);
    			parent = child;;
    			child = parent * 2 + 1;
    		}
    		else
    		{
    			break;
    		}
    	}
    }
    
    void HeapSort(int *a, size_t n)
    {
    	assert(a);
    	int parent = (n - 2) >> 1;
    	//建堆
    	for (; parent >= 0; --parent)
    	{
    		AdjustDown(a, n, parent);
    	}
    	for (int i = n - 1; i >= 0; --i)
    	{
    		swap(a[0], a[i]);
    		AdjustDown(a, i, 0);
    	}
    }
    
    void printArray(int *a, size_t n)
    {
    	for (size_t i = 0; i < n; i++)
    	{
    		cout << a[i] << " ";
    	}
    	cout << endl;
    }
    
    int main()
    {
    	//int arr[] = { 1, 3, 5, 7, 0, 2, 9, 4, 6, 8 };
    	int arr[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
    	int n = sizeof(arr) / sizeof(arr[0]);
    	HeapSort(arr, n); 
    	cout << "进行堆排序后：";
    	printArray(arr, n);
    	system("pause");
    	return 0;
    }

运行结果如下：

![Center][]

[Center]: /images/20220616/92b5421cc5514400a1d6360c55261836.png