#include "stdafx.h"
#pragma warning(disable:4996)
char h[101];//堆数组
int n;//堆大小，就是堆有几个元素
//传的参数是下标，通过下标交换元素值
void swap(int x, int y)
{
char t;//存储最小的结点编号
t = h[x];
h[x] = h[y];
h[y] = t;
return;
}
//大的数值向下压
void siftdown(int i)
{
int t, flag = 0;//flag是0的时候需要调整；1不用调整
//当i结点至少有左儿子并且需要继续调整的时候就执行循环
while (i * 2 <= n&&flag == 0)
{
//t记录左右孩子和自己三者中较小的数值
if (h[i] > h[i * 2])
t = i * 2;
else
t = i;
//先做左儿子的循环，再做右儿子循环，假如有右儿子的话
if (i * 2 + 1 <= n)
{
if (h[t] > h[i * 2 + 1])
t = i * 2 + 1;
}
//如果最小的编号不是自己，就与最小的交换
if (t != i)
{
swap(t, i);
i = t;//交换完以后t向下循环直至调整完全
}
else
flag = 1;
}
return;
}
//建立堆
void creat()
{
int i;
//从最后一个非叶结点到第1个结点依次进行向下调整
for (i = n / 2; i >= 1; i--)
{
siftdown(i);
}
return;
}
//删除堆最大的元素，其实也就是把最小的元素输出
char deletemax()
{
char c;
c = h[1];//临时变量记录堆顶的元素，也就是最小的元素
h[1] = h[n];//记录完毕，用最大的元素覆盖最小的元素的位置
n--;//相当于把上一步的堆顶元素删除
siftdown(1);//每次冒泡一个大元素都要调整一次，使得堆在每次删除最小元素以后仍是最小堆
return c;
}
int main()
{
int i=1;
int num;
char ch;//接收输入的字符
//读入要排序的数字的个数
//scanf("%d", &num);
//通过键盘读入来初始化堆数组
while ((ch) = getchar() != '\n')
h[i++] = ch;
//num = sizeof(h) / sizeof(int);
n = num=i-1;
//建堆
creat();
//连续执行删除操作，也就是把数值从小到大输出来
for (i = 1; i <= num; i++)
{
printf("%c", deletemax());
}
return 0;
}
用堆，排序输入的字符“tree”
