// 排序系列--堆排序.cpp : 定义控制台应用程序的入口点。
//说明：堆排序其实是对简单选择排序的一种改进算法，因为简单的选择排序在每次比较时没有保存上一趟比较的结果
//导致对前一趟做过的比较有重复了一次，这样就会大大降低效率，而堆排序就可以保存每次的比较结果
//在vs2010上编译通过
//堆排序思想：堆是具有以下性质的完全二叉树（数据结构--树）
//1，小根堆：每个节点的值小于等于左右孩子节点的值
//2，大根堆：每个节点的值大于等于左右孩子节点的值
//对于堆排序，首先要构造堆，然后将堆处理成小根堆或者大根堆，最后才是排序
#include "stdafx.h"
#include <ctime>//用于调用随机种子函数
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
void HeapAdjust(int a[],int i,int size) //调整堆,a是欲排序的数组，i是要进行处理的非叶子节点的元素，size是数组元素长度
{
int lchild=2*i; //i的左孩子节点序号 （因为是完全二叉树，这是固定的）
int rchild=2*i+1; //i的右孩子节点序号 （因为是完全二叉树，这是固定的）
int max=i; //临时变量，保存父节点
if(i<=size/2) //如果i是叶节点就不用进行调整
{
if(lchild<=size&&a[lchild]>a[max])//判断左孩子是否比父节点大，如果满足，就交换记录，否则执行下一步
{
max=lchild;
}
if(rchild<=size&&a[rchild]>a[max])//判断右孩子是否比父节点大，如果满足，就交换记录，否则执行下一步
{
max=rchild;
}
if(max!=i)//判断上面两个判断是否执行，如果执行了，必定max和i不等，否则max就等于i,这样就不必调整了
{
swap(a[i],a[max]);//std里的算法
HeapAdjust(a,max,size); //避免调整之后以max为父节点的子树不是堆
}
}
}
void BuildHeap(int a[],int size) //建立堆
{
int i;
for(i=size/2;i>=0;i--) //非叶节点最大序号值为size/2 (这是固定的)
{
HeapAdjust(a,i,size); //调整堆为大根堆
}
}
void HeapSort(int a[],int size) //堆排序
{
int i;
BuildHeap(a,size);
for(i=size-1;i>=0;i--)
{
swap(a[0],a[i]); //交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面
HeapAdjust(a,0,i-1); //重新调整堆顶节点成为大顶堆
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[20];
srand( (unsigned)time(NULL) );
for (int i=0;i<20;i++)
{
a[i]=rand()%40;
}
HeapSort(a,20);
for (int i=0;i<20;i++)
{
cout<<a[i]<<" ";
}
system("pause");
return 0;
}