github 地址：https://github.com/ImTangYun/comprehensive/blob/master/C%2B%2B/algorithm/heap_sort/heap_sort.cpp

// heapsort.cpp : 定义控制台应用程序的入口点。

#include "stdafx.h"

#include<iostream>

#include<algorithm>

using namespace std;

int left(int root){//求节点左节点

 return 2*root + 1;

}

int right(int root){//求右节点

 return 2*root + 2;

}

int parent(int child){//求父节点

 return (child-1)/2;

}

void heapify(int *a,int node,int heap_size){//调整节点使其满足堆得性质

 int l = left(node);

 int r = right(node);

 int largest = node;

 /*从left right node中选最大的节点作为根节点，如果根节点与孩子节点有过交换过程，就递归的对于其进行交换过程的孩子进行调整*/

 if(a[l] > a[largest]&&l < heap_size){

  largest = l;

 }

 if(a[r] > a[largest]&&l < heap_size){

  largest = r; 

 }

 if(largest != node){

  int temp = a[largest];

  a[largest] = a[node];

  a[node] = temp;

  heapify(a,largest,heap_size);

 }

}

void build_max_heap(int *a,int heap_size){//构造最大堆

 for(int i = (heap_size-1)/2;i >=0;--i ){

  heapify(a,i,heap_size);

 }

}

void heap_sort(int *a,int length){//堆排序算法

 build_max_heap(a,length);

 int temp = 0;

 for(int i = length-1;i >=0;--i){//每次通过调整将最大值放到a[0]，然后和末尾数字交换，在调整重复至数组有序

  swap(a[0],a[i]);

  heapify(a,0,i-1);

 }

}

int _tmain(int argc, _TCHAR* argv[])

{

 int a[] = {2,3,4,456,64,4,5,1,5,8};

 heap_sort(a,10);

 for(int i = 0;i < 10;++i){

  cout<<a[i]<<" ";

 }

 while(1);

 return 0;

}