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