学步园

/*
 * heapSort.cpp(堆排序)
 *
 *  Created on: 2012-4-17
 *      Author: jiyiqin
 *
 *  稳定性：
 	 *  堆排序类似于选择排序，所以不是一种稳定的排序。
 *
 *  代价：
 	 *  但是其时间复杂度最差也是o(n log n)，空间复杂度为1
 *
 *  算法描述
	 *  输入一个数组，构成一颗完全二叉树
	 *
	 *  (1)构造最大堆：对数组中每一个非叶子节点(0~n/2)进行堆化；
	 *  (2)迭代进行：
	 *  	删除堆顶；
	 *  	堆化整棵树；
 */
#include <iostream>
using namespace std;

class HeapSort{
private:
	int heapSize;

	void swap(int *a, int *b){
		*a = *a + *b;
		*b = *a - *b;
		*a = *a - *b;
	}

public:

	HeapSort(int heapSize){
		this->heapSize = heapSize;
	}

	/**
	 * 堆化一个子树
	 * 注意：
	 * 一个最大堆的根一定是最大的，并且
	 * 第二大的元素一定是其左/右孩子中的一个
	 *
	 * 递归将root下降，同时最大的元素也会上升
	 * */
	void maxHeap(int a[], int root){	//递归将根下降(注意越界判断)
		int largest_child = root;

		//和左孩子比较
		if(2*root < heapSize && a[root] < a[2*root]){
			largest_child = 2*root;
		}

		//和右孩子比较
		if((2*root + 1) < heapSize && a[largest_child] < a[2*root+1]){
			largest_child = 2*root+1;
		}

		//如果某个孩子更大
		if(largest_child != root){
			swap(&a[root], &a[largest_child]);	//下降
			maxHeap(a, largest_child);			//递归继续下降*
		}
	}

	/**
	 * 堆排序
	 * */
	void heapSort(int a[], int size){

		//自底向上构造最大堆
		for(int i = heapSize/2;i>=1;i--){
			maxHeap(a, i);
		}

		//不断删除根+堆化整棵树
		for(i=1;i<=size;i++){
			swap(&a[1],&a[heapSize]);
			cout<<a[heapSize]<<" ";

			maxHeap(a, 1);
			heapSize--;
		}
	}

	/**
	 * 随机填充一个数组
	 * */
	void radomArray(int a[], int size){
		for(int i=0;i<size;i++){
			a[i] = rand() % size;
		}
	}

};

int main(){

	int heapSize = 15;
	int arraySize = heapSize+1;		//heap begin from 1	
	int *a = new int[arraySize];	//heap
	HeapSort maxHeap(heapSize);

	//随机生成一个数组
	maxHeap.radomArray(a, arraySize);
	for(int i=1;i<arraySize;i++){
		cout<<a[i]<<" ";
	}
	cout<<endl;

	//进行堆排序
	maxHeap.heapSort(a, heapSize);
	return 0;
}