Question

跪求数据结构：堆排序算法演示

要求输入元素序列采用堆排序进行排序，并将依据树状结构在屏幕上输出层次遍历的结果·· 跪求大侠帮忙了！

Answer 1

《C算法》——堆排序

堆排序(Heap Sort)只需要一个记录大小的辅助空间
堆排序在最坏的情况下，其时间复杂度为O(nlog n),相对于快速排序来说，这是堆的最大优点。
堆是一棵完全二叉树，且树中不存在大于（小于）父节点的节点。
堆中的第i个元素大于或等于第2i个元素和第2i+1个元素。

自底向上的堆化

fixUp(Item* a, int k)
...{
while(k>1 && less(a[k/2], a[k]))
...{
exch(a[k], a[k/2]);
k = k / 2; //向上找到父结点
}
}
--------------------------------------------------------------------------------
自顶向下的堆化 fixDown(Item* a, int k, int N)
...{
int j;
while(2*k <= N)
...{
j = 2 * k;
if(j<N && less(a[j], a[j+1])) j++; //选择两个孩子中较大者，与a[k]比较
if(!less(a[k], a[j])) break; //局部满足堆条件，立即退出
exch(a[k], a[j]); //否则，交换
k = j;
}
}
--------------------------------------------------------------------------------
堆排序 void heapsort(Item* a, int l, int r)
...{
int k, N = r-l+1; //N为待排元素的个数
for(k = N/2; k >= 1; k--) //建堆，从第一个非叶子节点开始
fixDown(a, k, N); //自顶向下的堆化
while(N > 1)
...{
exch(a[l], a[l+N-1]); //把第一个元素（最大）和最后一个元素交换
fixDown(a, 1, --N); //再自顶向下堆化
}
}

Answer 2

试一下这个吧，pascal语言的，没用指针，应该没有错吧。

program heapsort;
var
i,j,n : longint;
a : array[0..100001] of longint;

procedure xianxu_visit(i : longint);
begin
write(a[i],' ');
if 2*i <= n then
xianxu_visit(2*i);
if 2*i < n then
xianxu_visit(2*i+1);
end;

procedure zhongxu_visit(i : longint);
begin
if 2*i <= n then
zhongxu_visit(2*i);
write(a[i],' ');
if 2*i < n then
zhongxu_visit(2*i + 1);
end;

procedure houxu_visit(i : longint);
begin
if 2*i <= n then
houxu_visit(2*i);
if 2*i < n then
houxu_visit(2*i+1);
write(a[i],' ');
end;

procedure heap(l,m : longint);
var
i,j,t : longint;
begin
i := l;
j := i*2;
t := a[l];
while j <= m do
begin
if ( j < m ) and ( a[j] < a[j+1] ) then
inc(j);
if t < a[j] then
begin
a[i] := a[j];
i := j;
j := 2*i;
end
else
break;
end;
a[i] := t;
end; //heap
begin
assign(input,'heapsort.in'); reset(input);
assign(output,'heapsort.out'); rewrite(output);
readln(n);
for i :=1 to n do
read(a[i]);
for i := n div 2 downto 1 do
heap(i,n);
for i := n downto 2 do
begin
a[0] := a[1];
a[1] := a[i];
a[i] := a[0];
heap(1,i-1);
end;
for i:= 1 to n do
write(a[i],' ');
writeln;
xianxu_visit(1); writeln;
zhongxu_visit(1); writeln;
houxu_visit(1); writeln;
close(input);
close(output);
end.

Answer 3

#include <stdio.h>
void adjust(int *list,const int root,const int n);
void HeapSort(int *list,const int n)
{
int i=0;
for(i=n/2;i>=1;i--)
adjust(list,i-1,n);
int t=list[n];
list[n]=list[0];
list[0]=t;
if(n>1)
HeapSort(list,n-1);
else
{
int t=list[1];
list[1]=list[0];
list[0]=t;
}
}
void adjust(int *list,const int root,const int n)
{
int e=list[root];
int k=e,j=0;
for(j=2*root;j<=n;j*=2)
{
if(j<n)
if(list[j]<list[j+1])
j++;
if(k>=list[j])
break;
list[j/2]=list[j];
}
list[j/2]=e;
}
int main(int argc,char **argv)
{
int i=0;
int src[10]={26,5,77,1,61,11,59,15,48,19};
HeapSort(src,9);
i=0;
while(i<10)
{
printf("%d,",src[i]);
i++;
}
}

Answer 4

你这个没有现成的，推荐个网站：编程论坛