算法导论 第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);
	}
}

算法导论 第6章 堆排序,布布扣,bubuko.com

算法导论 第6章 堆排序

原文：http://blog.csdn.net/lucienduan/article/details/38391231