堆排序与二叉树排序

堆排序与二叉树排序

1.堆排序

堆：设有数据元素的集合（R1,R2,R3,...Rn)它们是一棵顺序二叉树的结点且有

      Ri<=R2i 和Ri<=R2i+1(或>=)

堆的性质：堆的根结点上的元素是堆中的最小元素，且堆的每一条路径上的元素都是有序的。

堆排序的思想是：

1）建初始堆（将结点[n/2],[ n/2]-1,...3,2,1分别调成堆）

2）当未排序完时

输出堆顶元素，删除堆顶元素，将剩余的元素重新建堆。

程序如下：

program duipx;
const n=8;
type arr=array[1..n] of integer;
var a:arr;i:integer;
procedure sift(var a:arr;l,m:integer);
var i,j, t:integer;
begin
i:=l;j:=2*i;t:=a;
while j<=m do
  begin
   if (j<m) and (a[j]>a[j+1]) then j:=j+1;
   if t>a[j] then
      begin a:=a[j];i:=j;j:=2*i; end
             elseexit;
  a:=t;
end;

end;
begin
for i:=1 to n do read(a);
for i:=(n div 2) downto 1 do
  sift(a,i,n);
for i:=n downto 2 do
  begin
  write(a[1]:4);
  a[1]:=a;
  sift(a,1,i-1);
  end;
  writeln(a[1]:4);
end.

2.二叉树排序

排序二叉树：每一个参加排列的数据对应二叉树的一个结点，且任一结点如果有左（右）子树，则左（右）子树各结点的数据必须小（大）于该结点的数据。中序遍历排序二叉树即得排序结果。程序如下：

program pxtree;
const
a:array[1..8] of integer=(10,18,3,8,12,2,7,3);
type point=^nod;
     nod=record
     w:integer;
     right,left:point ;
     end;
var root,first:point;k:boolean;i:integer;
procedure hyt(d:integer;var p:point);
begin
  if p=nil then
   begin
    new(p);
    with p^ do begin w:=d;right:=nil;left:=nil end;
    if k then begin root:=p; k:=false end;
   end
  else with p^ do if d>=w then hyt(d,right) else hyt(d,left);
end;
procedure hyt1(p:point);
begin
  with p^ do
   begin
    if left<>nil then hyt1(left);
    write(w:4);
    if right<>nil then hyt1(right);
   end
end;
begin
first:=nil;k:=true;
for i:=1 to 8 do hyt(a,first);
hyt1(root);writeln;
end.

返回