堆排序学习以及模板
堆排序（Heapsort）是指利用堆这样的数据结构所设计的一种排序算法。
堆积是一个近似全然二叉树的结构。并同一时候满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆排序的平均时间复杂度为Ο(nlogn) 。
算法步骤：
1、创建一个堆H[0..n-1]（利用MaxHeapify函数从最后一个非叶子节点開始调整堆，如BuildMaxHeap函数调整为大根堆。这个大根堆并不能保证全部的父节点都比子节点大。可是根节点一定是整个堆中最大的）。
2、把堆首（最大值）和堆尾互换（取堆顶元素。由于其总是当前堆中最大或者最小的）
3、把堆的尺寸缩小1，并调用MaxHeapify,目的是使堆顶元素仍然是堆中最大或者最小的（最大还是最小看是大根堆还是小根堆）。
4、反复步骤2，直到堆的尺寸为1
#include <stdio.h>
#include <stdarg.h>
int getParent(int i) //获取父节点
{
return (int)(i/2);
}
int getLeftSon(int i) //左孩子节点
{
return (i*2);
}
int getRightSon(int i) //右孩子节点
{
return (i*2 + 1);
}
void PrintHeap(int a[], int size,char *msg, ...)
{
int i;
va_list ap;
char buffer[1024];
va_start(ap, msg); //输出自己定义内容
vsnprintf(buffer, 1024, msg, ap);
va_end(ap);
printf("%s",buffer);
for(i=1; i<=size; i++)
printf("%d ",a[i]);
printf("
");
}
//调整以某个节点i为根节点的子树为大根堆
void MaxHeapify(int a[], int i, int HeapSize)
{
int left_son = getLeftSon(i);
int right_son = getRightSon(i);
int max_num = i;
if(left_son <= HeapSize && a[left_son] > a[max_num] )
{
max_num = left_son;
}
if(right_son <= HeapSize && a[right_son] > a[max_num]) //两步 找出最大的节点
{
max_num = right_son;
}
if(max_num != i)
{
int temp = a[i];
a[i] = a[max_num];
a[max_num] = temp;
MaxHeapify(a, max_num, HeapSize);
}
}
//首先将一个无序数组 组建成为一个大根堆
void BuildMaxHeap(int a[], int size)
{
int i;
for(i=(int)(size/2); i>0; i--) //从最后一个非叶子节点開始往前递归
{
MaxHeapify(a, i, size);
}
PrintHeap(a, size, "Build a Big root Heap %d:",size);
}
//先建一个大根堆 然后从后往前取最大的数（根节点肯定是当前堆中最大的数 每次堆大小减一）
void HeapSort(int a[], int size)
{
int i;
BuildMaxHeap(a, size);
for(i=size; i>1; i--)
{
int temp = a[i]; //获取当前堆中最大的数
a[i] = a[1];
a[1] = temp;
MaxHeapify(a, 1, i-1);
PrintHeap(a, i-1, "This is in Heap sorting:");
}
}
int main()
{
//从1開始 建堆
int Array[] = {0, 6, 8, 4, 10, 2, 5, 7, 1, 3, 9};
HeapSort(Array, 10);
PrintHeap(Array, 10, "After Heap Sort, Array is:");
return 0;
} 执行结果：
參考网址：