前言
对于推排序它像合并排序而不像插入排序，堆排序的运行时间为O(nlogn)。像插入排序而不像合并排序，它是一种原地排序算法：在任何时候，数组中只有常数和元素存储在输入数组以外。这样堆排序就拥有了两种排序算法的优点。
堆算法中涉及到的主要算法有：维持最大堆（Max_Heapify）和建立堆（Build_Max_Heap）。
1. 编码实现
这里为了使得数组的下标是从1开始计算的，在数组的首部插入了元素-1 。
1.1 维护最大堆
//维持堆性质
int heap_size = 0; //堆中元素
void Max_Heapify(std::vector<int>& vec, int pos) //pos为当前操作的根位置
{
int left(pos*2);
int right(pos*2+1);
//求出最大的根节点
int root_pos(-1);
if(left<=heap_size && vec[pos]<vec[left])
{
root_pos = left;
}
else
{
root_pos = pos;
}
if(right<=heap_size && vec[root_pos]<vec[right])
{
root_pos = right;
}
//不满足最大堆的性质了，因为比较之后求出来的根节点和输入的节点不一样
if(root_pos != pos)
{
std::swap(vec[root_pos], vec[pos]);
Max_Heapify(vec, root_pos);
}
}
1.2 创建最大堆
//创建堆
void Build_Max_Heap(std::vector<int>& vec)
{
//由于堆中有heap_size/2~heap_size 的元素为叶子节点，因而只需要迭代heap_size/2次
for(int i=(heap_size/2); i>=1; --i)
{
Max_Heapify(vec, i);
}
}
1.3 堆排序
//堆算法
void HeapSort(std::vector<int>& vec)
{
int len(vec.size());
if(len == 0) return;
cout << "display origin array:" << endl;
for_each(vec.begin(), vec.end(), Disp<int>()); //打印原始的数据
std::vector<int> temp = vec;
heap_size = vec.size();
temp.insert(temp.begin(), -1);
Build_Max_Heap(temp);
int loop = heap_size;
for(int i=heap_size; i>=1; --i)
{
vec[i-1] = temp[1];
std::swap(temp[1], temp[i]);
temp.pop_back();
--heap_size;
Max_Heapify(temp, 1);
}
cout << "\narray sorted:" << endl;
for_each(vec.begin(), vec.end(), Disp<int>());
}
