堆排序

基本思想

1.堆排序 堆：设有数据元素的集合（R1,R2,R3,...Rn)它们是一棵顺序二叉树的结点且有Ri<=R2i和Ri<=R2i+1(或>=) 堆的性质：堆的根结点上的元素是堆中的最小元素，且堆的每一条路径上的元素都是有序的。 堆排序的思想是： 1）建初始堆（将结点[n/2],[ n/2]-1,...3,2,1分别调成堆） 2）当未排序完时 输出堆顶元素，删除堆顶元素，将剩余的元素重新建堆。

代码

PASCAL

C++

算法实例

例1

输入若干个数（范围在0到9），用堆储存，然后由小到大输出。 程序：

 
program heap;
 var
  i,j,n:longint;
  a:array[0..100] of longint;
  procedure init;
    var
      i,j:longint;
    begin
      fillchar(a,sizeof(a),0);
      a[0]:=-maxlongint;
      n:=0;
    end;
  procedure swap(i,j:longint);
    var
      k:longint;
    begin
      k:=a[i];
      a[i]:=a[j];
      a[j]:=k;
    end;
  procedure father;
    var
      i,j:longint;
    begin
      i:=n;
      while a[i]<a[i div 2] do
        begin
          swap(i,i div 2);
          i:=i div 2;
        end;
    end;
  procedure son(k:longint);
    var
      i,j:longint;
    begin
          if (k*2+1<=n)and(a[k*2+1]<a[k])//如果结点K有一个比它小的右子结点
            then begin
                   swap(k,k*2+1);
                   if a[k]>a[k*2]//如果调整右结点后，结点K比它的左结点小
                     then begin
                            swap(k,k*2);
                            son(k*2);//调整左子树
                          end;
                   son(k*2+1);//调整右子树
                 end
            else begin
                   if (k*2<=n)and(a[k*2]<a[k])//如果结点K有一个比它小的左子结点
                     then begin
                            swap(k,k*2);
                            son(k*2);//调整左子树
                          end;
                 end;
    end;
  procedure main;
    var
      i,j:longint;
      c:char;
    begin
      repeat
        readln(c);
      until c in ['e','0'..'9'];
      while c<>'e' do//当输入为e时输入结束
        begin
          inc(n);
          a[n]:=ord(c)-48;
          father;//调整结点a[n]
          repeat
            readln(c);
          until c in ['e','0'..'9'];
        end;
      for i:=1 to n do
        begin
          writeln(a[1]);
          a[1]:=a[n];//将堆末元素与堆顶元素交换，删除堆末元素。
          dec(n);
          son(1);从堆顶开始调整堆
        end;
    end;
 begin
  assign(input,'1.txt');
  reset(input);
  init;
  main;
  close(input);
 end.

例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[i];
 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[i]:=a[j];i:=j;j:=2*i; end
             else exit;
  a[i]:=t;
 end;
end;
begin
 for i:=1 to n do read(a[i]);
 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[i];
  sift(a,1,i-1);
  end;
  writeln(a[1]:4);
end.

参见

• 堆

堆排序是一个小作品，欢迎帮助扩充这个条目。