/*
// 所谓的堆排序就是二叉树顺序存储。
// 其算法思想就是建堆a[0~n-1]->堆顶a[0]与堆底a[n-1]（数组最后一个元素）互换->建堆a[0~n-2]->堆顶a[0]与堆底a[n-2]互换->建堆a[0~n-3]......a[0~n-n]
// 嘛叫堆？业余的理解为二叉树左右子节点小于/大于父节点。子节点小于父节点的叫大堆，子节点大于父节点的叫小堆。
// 假如我们要把一个数组array[10]按照由小到大顺序排序。
// 1：将数组分为一个大堆（即一个父节点值大于子节点值的二叉树）
// 2：将堆的根节点与原始数组中的最后一个元素互换。这样，就保证了最后一个元素array[9]为最大值了。然后，再将array[0...8]分堆。
// 3：2操作一直执行下去，直到待分堆的元素为1。
*/
#include<stdio.h>
#include<stdlib.h>
int g_size;
void xfSwap(int& x,int& y)
{
int temp = x;
x = y;
y = temp;
}
/*
大堆排序 传说这段代码是算法导论中的。此处必须说明是转载，不过哥们不喜欢ctrl_c,ctrl_v，必要的还是要加入些自己的理解与思考。于是自己实现了小堆排序。
*/
int max_heapify(int A[],int i)
{
int l,r,largest;
//size = sizeof(A)/sizeof(int);
l = i*2+1;
r = i*2 + 2;
if(l < g_size && A[l] > A[i])
largest = l;
else
largest = i;
if(r < g_size && A[r] > A[largest])
largest = r;
if(largest != i)
{
xfSwap(A[i],A[largest]);
max_heapify(A,largest);
}
return 0;
}
int build_maxheap(int A[])
{
int i;
//size = sizeof(A)/sizeof(int);
for(i = (g_size-1)/2;i>=0;i--)
max_heapify(A,i);
return 0;
}
int maxheap_sort(int A[])
{
int i;
//size = sizeof(A)/sizeof(int);
build_maxheap(A);
for(i = g_size-1;i>0;i--)
{
xfSwap(A[0],A[i]);
g_size--;
max_heapify(A,0);
}
return 0;
}
/*
小堆排序 自己实现
*/
/*
保证i这个非叶子节点与它的子节点构成小堆
*/
void min_heapify(int A[],int i)
{
int l,r,smallest;
// 由于数组下标基于0
l = i*2+1;
r = i*2 + 2;
// 先将i与左孩子取小，smallest指向最小值
if(l < g_size && A[l] < A[i])
smallest = l;
else
smallest = i;
//将i的右孩子与smallest进行比较
if(r < g_size && A[r] < A[smallest])
smallest = r;
//如果smallest不是i节点，将i节点与子节点交换，同时，将交换后的子节点继续修成小堆
if(smallest != i)
{
xfSwap(A[i],A[smallest]);
min_heapify(A,smallest);
}
}
/*
将数组初始化为小堆
*/
void build_minheap(int a[])
{
int i=0;
for(i = (g_size-1)/2;i>=0;--i)//从最后一个非叶子节点向上逐个“筛选”
{
min_heapify(a,i);
}
}
void minheap_sort(int a[])
{
build_minheap(a);
for(int i=g_size-1;i>0;--i)
{
//互换第一个元素与最后一个元素，此时互换后的最后一个元素为最小元素，以后便不再参与小堆构建。
xfSwap(a[0],a[i]);
--g_size;
//由于进行a[0],a[i]的呼唤，所以需要对a[0]进行分堆操作。
min_heapify(a,0);
}
}
int main()
{
//int a[11]={49,38,52,44,81,97,76,13,27,65,66},i=0;
int a[10]={49,38,52,44,81,97,76,13,27,65},i=0;
g_size = sizeof(a)/sizeof(int);
printf("原始数据：\n");
for(i=0;i<g_size;i++)
printf("%d ",a[i]);
//maxheap_sort(a);
minheap_sort(a);
printf("\n堆排序后\n");
//print_heap(a);
g_size = sizeof(a)/sizeof(int);
for(i=0;i<g_size;i++)
printf("%d ",a[i]);
return 0;
}