堆排序

堆排序

堆：设有数据元素的集合（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;
  end;
  a:=t;
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.