首页 > 代码库 > 算法导论 第6章 堆排序

算法导论 第6章 堆排序

堆数据结构实际上是一种数组对象,是以数组的形式存储的,但是它可以被视为一颗完全二叉树,因此又叫二叉堆。堆分为以下两种类型:

大顶堆:父结点的值不小于其子结点的值,堆顶元素最大

小顶堆:父结点的值不大于其子结点的值,堆顶元素最小

堆排序的时间复杂度跟合并排序一样,都是O(nlgn),但是合并排序不是原地排序(原地排序:在排序过程中,只有常数个元素是保存在数组以外的空间),合并排序的所有元素都被拷贝到另外的数组空间中去,而堆排序是一个原地排序算法。

1、在堆排序中,我们通常使用大顶堆来实现,由于堆在操作上是被看着一颗完全二叉树,所以其高度为lgn,堆结构上的一些操作的时间复杂度也通常是O(lgn)。

/*
 *	算法导论 第六章 堆排序
 *	堆数据结构的实际存储是作为一个顺序数组来保存的
 *	对堆的操作是将它作为一个完全二叉树的结构来使用的
 *	堆排序分为以下几个步骤:
 *	首先是建立大顶堆,即函数buildMaxHeap,建堆实际上是利用堆的最大化调整(maxHeapify)自底向上来实现的
 *	然后是逐步将堆顶的最大元素交换到堆的结尾,堆的大小也不断缩小,然后再将堆最大化,从而实现排序
 *	
 *	其中建堆的时间复杂度为O(n),堆的最大化调整时间复杂度为O(lgn),所以总的
 *	时间复杂度是O(n*lgn+n),即O(nlgn)
 */
#include <iostream>
using namespace std;

void printArray(int arr[], int len);
void heapSort(int arr[], int len);
void maxHeapify(int arr[], int heapSize, int pos);
void buildMaxHeap(int arr[], int len);

int main()
{
	int arr[] = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1};
	int len = sizeof(arr) / sizeof(arr[0]);

	cout << "原数组:" << endl;
	printArray(arr, len);

	heapSort(arr, len);

	cout << "堆排序后的数组:" << endl;
	printArray(arr, len);

	return 0;
}

void printArray(int arr[], int len)
{
	for (int i=0; i<len; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}

void heapSort(int arr[], int len)
{
	buildMaxHeap(arr, len);
	for (int i=len-1; i>0; i--)
	{
		int temp = arr[0];
		arr[0] = arr[i];
		arr[i] = temp;
		maxHeapify(arr, i, 0);
	}
}

void maxHeapify(int arr[], int heapSize, int pos)
{
	int lPos = (pos + 1) * 2 - 1;
	int rPos = (pos + 1) * 2;
	int largest = pos;
	if (lPos < heapSize && arr[lPos] > arr[largest])
		largest = lPos;
	if (rPos < heapSize && arr[rPos] > arr[largest])
		largest = rPos;

	if (largest != pos)
	{
		int temp = arr[pos];
		arr[pos] = arr[largest];
		arr[largest] = temp;
		maxHeapify(arr, heapSize, largest);
	}
}

void buildMaxHeap(int arr[], int len)
{
	for (int i=len/2-1; i>=0; i--)
	{
		maxHeapify(arr, len, i);
	}
}

2、堆结构可以用来实现优先级队列,优先级队列是一组元素构成的集合,可以从中取出最大或者最小的元素,堆是优先级队列的一种很好的实现。通过堆,优先级队列上的任意操作可以再O(lgn)时间内实现。