本文主要是介绍建大顶堆和小顶堆及堆排序算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/************************************************************
Function: 堆排序
Author: glq2000[glq2000@126.com]
Date: Tues, 2010-8-3
Note:
写堆排序函数要注意两个问题
1. 如何由一个无序序列建立一个堆?
2. 如何在输出堆顶元素后,调整剩余元素成为一个新堆?
*************************************************************/
#include <iostream>
#include <cstring>
using namespace std;
void BigHeapAdjust(int *p, int r, int len); //大顶堆筛选函数
void BigHeapSort(int *p, int len); //大顶堆排序函数
void SmallHeapAdjust(int *p, int r, int len); //小顶堆筛选函数
void SmallHeapSort(int *p, int len); //小顶堆排序函数
int main()
{
int array[100] = {0}; //用于盛放待排序元素
int n; //待排序元素的个数,不要超过100
scanf("%d", &n);
for(int i=0; i<n; ++i)
scanf("%d", array+i);
BigHeapSort(array, n); //大顶堆排序,排序后数组元素从小到大排列
//SmallHeapSort(array, n); //小顶堆排序,排序后数组元素从大到小排列
for(int k=0; k<n; ++k)
printf("%d ", array[k]);
getchar();
getchar();
getchar();
return 0;
}
/********************************************************************
大顶堆筛选函数：
p: 待排序的数组
r: 需调整的那个元素的下标,注意数组的第n个元素的下标是n-1
len: 数组元素个数
********************************************************************/
void BigHeapAdjust(int *p, int r, int len)
{
int tmp = p[r];
int j;
for(j=2*r+1; j<=len-1; j=2*j+1) //沿节点值较大的儿子往下层筛选，2*r+1是左儿子，2*(r+1)是右儿子
{
if(j<len-1 && p[j+1]>=p[j]) //因为j<len-1时,p[j+1]才不会越界
++j; //如果右儿子大于左儿子,j++转移到右儿子,让j等于左右儿子中较大的那个
if(tmp >= p[j])
break;
p[r] = p[j]; //较大的儿子向父节点平移,并更新r节点的位置
r = j;
}
p[r] = tmp; //将根节点放置到最后空出的合适的位置
}
/*******************************
大顶堆排序函数：
p： 待排序的数组
len: 数组元素个数
********************************/
void BigHeapSort(int *p, int len)
{
int i,j;
//对完全二叉树来说,共len/2个非叶子节点,下标为len/2-1的元素是最后一个非叶子节点
//从最后一个非叶子节点起倒序,用HeapAdjust函数来调整,初建大顶堆,使各个根节点含有最大的key
for(i=len/2-1; i>=0; --i)
BigHeapAdjust(p, i, len);
p[0] ^= p[len-1];
p[len-1] ^= p[0];
p[0] ^= p[len-1]; //以上为交换堆顶和堆底,下面开始调整一次,交换一次
for(j=len-1; j>1; --j) //此处一开始写成了j>0,其实j>1即可;因为j=2时,等HeapAdjust调整完毕并交换后,整个数组已有序
{
BigHeapAdjust(p, 0, j);
//交换堆顶和堆底
p[0] ^= p[j-1];
p[j-1] ^= p[0];
p[0] ^= p[j-1];
}
}
/*******************************************************************
小顶堆筛选函数：
p: 待排序的数组
r: 需调整的那个元素的下标,注意数组的第n个元素的下标是n-1
len: 数组元素个数
********************************************************************/
void SmallHeapAdjust(int *p, int r, int len)
{
int tmp = p[r];
int j;
for(j=2*r+1; j<=len-1; j=2*j+1) //沿节点值较小的儿子往下层筛选,2*r+1是左儿子，2*(r+1)是右儿子
{
if(j<len-1 && p[j+1]<=p[j]) //因为j<len-1时,p[j+1]才不会越界
++j; //如果右儿子小于左儿子,j++转移到右儿子,让j等于左右儿子中较小的那个
if(tmp <= p[j])
break;
p[r] = p[j]; //较小的儿子向父节点平移,并更新r节点的位置
r = j;
}
p[r] = tmp; //将根节点放置到最后空出的合适的位置
}
/*******************************
小顶堆排序函数：
p： 待排序的数组
len: 数组元素个数
********************************/
void SmallHeapSort(int *p, int len)
{
int i,j;
//对完全二叉树来说,共len/2个非叶子节点,下标为len/2-1的元素是最后一个非叶子节点
//从最后一个非叶子节点起倒序,用HeapAdjust函数来调整,初建大顶堆,使各个根节点含有最大的key
for(i=len/2-1; i>=0; --i)
SmallHeapAdjust(p, i, len);
p[0] ^= p[len-1];
p[len-1] ^= p[0];
p[0] ^= p[len-1]; //以上为交换堆顶和堆底,下面开始调整一次,交换一次
for(j=len-1; j>1; --j) //从根开始调整,调完后交换堆顶和堆底
{
SmallHeapAdjust(p, 0, j);
//交换堆顶和堆底
p[0] ^= p[j-1];
p[j-1] ^= p[0];
p[0] ^= p[j-1];
}
}
这篇关于建大顶堆和小顶堆及堆排序算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
