首页 > 代码库 > 堆排序

堆排序

二叉堆:

二叉堆是完全二叉树或者是近似完全二叉树。

二叉堆满足二个特性:

1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。

2.每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)。

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆

堆排序:
 由二叉堆的定义可知,堆顶元素(即二叉堆的根节点)一定为堆中的最大值或最小值,因此如果我们输出堆顶元素后,将剩余的元素再调整为二叉堆,继而再次输出堆顶元素,再将剩余的元素调整为二叉堆,反复执行该过程,这样便可输出一个有序序列,这个过程我们就叫做堆排序。
时间复杂度O(N*logN)

实现:

/************************************************
堆排序
by Rowandjj
2014/7/23
************************************************/
#include<iostream>
using namespace std;
//数组arr,除了start位置上的元素不满足大顶堆的性质,
//其他元素均满足,此函数的作用是使数组从start到end都满足大顶堆的性质
void HeapAdjust(int arr[],int start,int end)
{
	int temp = arr[start];//记录不满足大顶堆性质的元素
	int i = start*2+1;//i为其左孩子序号
	while(i<=end)
	{
		if(i+1<=end && arr[i+1]>arr[i])//获取左右孩子较大的孩子的序号(如果有右孩子的话)
		{
			i++;
		}
		if(temp >= arr[i])//如果满足大顶堆性质那么无须操作
		{
			break;
		}
		arr[start] = arr[i];//否则最大的子节点向上移动,替换掉其父节点  
		start = i;//判断其子树是否满足大顶堆性质
		i = i*2+1;
	}
	arr[start] = temp;
}

void HeapSort(int arr[],int len)
{
	if(arr == NULL || len <= 0)
	{
		return;
	}
	int i;
	for(i = len/2-1; i >= 0; i--)//将无序数组构建成大顶堆,从第一个非叶子节点开始建堆
	{
		HeapAdjust(arr,i,len-1);		
	}
	for(i = len-1; i > 0; i--)//每次都将堆顶元素(最大元素)与堆尾元素互换,然后去掉堆尾元素,对其他元素进行建堆操作
	{
		int temp = arr[i];
		arr[i] = arr[0];
		arr[0] = temp;
		HeapAdjust(arr,0,i-1);
	}
}
int main()
{
	int arr[] = {6,1,3,1,5,4,2,7};
	HeapSort(arr,8);
	for(int i = 0; i < 8; i++)
	{
		cout<<arr[i]<<" ";
	}
	cout<<endl;
	return 0;
}