堆(英语:heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:
堆中某个节点的值总是不大于或不小于其父节点的值;
堆总是一棵完全二叉树。
将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
本次主要来学习一下关于堆排序算法,本代码参考了白话经典算法的堆与堆排序,里面讲了堆的操作和堆排序,需要了解详细的请阅读原文。

#include <stdio.h>
#include <stdlib.h>
void MinHeapFixdown(int a[],int i,int n)
{
	int j,temp;
	temp=a[i];
	j=2*i+1;
	while(j<n)
	{
		if(j+1<n&&a[j+1]<a[j])
			j++;
		if(a[j]>=temp)
			break;
		a[i]=a[j];
		i=j;
		j=2*i+1;
	}
	a[i]=temp;
}
//建立最小堆
void MakeMinHeap(int a[],int n)
{
	for(int i=n/2-1;i>=0;i--)
		MinHeapFixdown(a,i,n);
}
//堆排序(从大到小)
void MinHeapsort(int arr[],int n)
{
	for(int i=n-1;i>=1;i--)
	{
		int temp=0;
		temp=arr[0];
		arr[0]=arr[i];
		arr[i]=temp;
		MinHeapFixdown(arr,0,i);
	}
}
int main()
{
	int arr[10]={2,5,8,3,4,1,7,9,0,6};
    //将数组转换为最小堆形式
	MakeMinHeap(arr,10);
    //对其进行排序
	MinHeapsort(arr,10);
	for(int i=0;i<10;i++)
	{
		printf("%d",arr[i]);
	}
	return 0;
}

阅读原文