ヒープソート～Delphiソースコード集

ヒープソートは完全２分木の構造を活かしたソートアルゴリズムで並び替えを行います。
配列の添え字が0から始まっている場合、ヒープ構造は以下のようになります。
ノードには左の子ノードと右の子ノードの２つがありますが、
最下層のノードには子ノードが無く、
最下層の１つ前の層は子ノードが２個、又は１個、又は0個となります。

                  a[0]               最上層
                ／   ＼
              ／       ＼
            ／           ＼
         a[1]            a[2]        ２層目
        ／ ＼            ／ ＼
      ／     ＼        ／     ＼
   a[3]       a[4]  a[5]      a[6]   ３層目
   ／ ＼      ／
a[7]  a[8]  a[9]                     最下層

配列の添え字が0から始まっている場合、
添え字が[0]のノードは根ノードで、
添え字が[奇数]のノードは左の子ノード、
添え字が[偶数]のノードは右の子ノードです。

         a[0] 根ノード
       ／   ＼
     ／       ＼
   ／           ＼
a[1]            a[2]
奇数なので      偶数なので
左の子ノード    右の子ノード

配列の添え字が0から始まっている場合、
ある親の添え字を [P] とすると、
　左の子の添え字は L ＝ P×2 ＋1
　右の子の添え字は R ＝ P×2 ＋2
となります。

       a[P]
     ／   ＼
   ／       ＼
a[L]        a[R]
L＝P×2＋1  R＝P×2＋2

配列の添え字が0から始まっている場合、
あるノードの添え字が [C] とすると、
　その親ノードの添え字 P ＝小数点以下切り捨て( (C－1)÷2 )
となります。

       a[P]    P ＝ 切り捨て( (L－1)÷2 )
     ／   ＼   P ＝ 切り捨て( (R－1)÷2 )
   ／       ＼
a[L]        a[R]

ヒープソートのソースコード

新規プロジェクトを作成し、TButton×１個、TMemo×１個をフォームへドラッグ＆ドロップします。
以下ソースコードをコピー＆ペーストし、
Button1.OnClickイベントプロパティに Button1Click を設定してください。

unit Unit1;

interface

uses
  Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
  Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls;

type
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
  private
    { Private 宣言 }
  public
    { Public 宣言 }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

//ヒープソートで配列を昇順に並べる（速くないがメモリやスタックを消費しない）
procedure HeapSort(var Arr:Array of Integer);
  //二つの整数の値を入れ替える
  procedure SwapInt(var v1,v2:Integer);
  var sw:Integer;
  begin
    sw:=v1;
    v1:=v2;
    v2:=sw;
  end;
var NoSorted:Integer;//未ソートの添え字
    LeftChildIdx, RightChildIdx:integer;
    ParentIdx:integer;
    MaxParentIdx:Integer;
begin
  //最後のノードから確定していく
  //処理開始時は 0～最後(NoSorted)の全てのノードがソートされていない
  NoSorted:=High(Arr);
  while NoSorted>0 do
  begin
    //未ソートノード内で子ノードが１つ以上あるノードの添え字の最大値を求める
    MaxParentIdx:=(NoSorted-1) div 2;
    for ParentIdx := MaxParentIdx downto 0 do
    begin
      //左の子ノードの添え字
      LeftChildIdx:=ParentIdx*2+1;
      //右の子ノードの添え字
      RightChildIdx:=ParentIdx*2+2;
      if RightChildIdx<=NoSorted then
      begin
        //左右に子がある
        if Arr[LeftChildIdx]>Arr[RightChildIdx] then
        begin
          //左>右 ⇒ 親と左を比較
          if Arr[ParentIdx]<Arr[LeftChildIdx] then
            SwapInt(Arr[ParentIdx],Arr[LeftChildIdx]);
        end
        else
        begin
          //左≦右 ⇒ 親と右を比較
          if Arr[ParentIdx]<Arr[RightChildIdx] then
            SwapInt(Arr[ParentIdx],Arr[RightChildIdx]);
        end;
      end
      else
      begin
        //左だけ子が存在 ⇒ 親と左を比較
        if Arr[ParentIdx]<Arr[LeftChildIdx] then
          SwapInt(Arr[ParentIdx],Arr[LeftChildIdx]);
      end;
    end;
    //最大値が根ノードArr[0]に入っているので、
    //根ノードArr[0]と枝ノードArr[NoSorted]を入れ替えて、枝ノードArr[NoSorted]のソートが完了
    SwapInt(Arr[0], Arr[NoSorted]);
    //枝ノードArr[NoSorted]のソートが完了したのでNoSortedの値１つを減らす
    Dec(NoSorted);
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var Arr:Array of Integer;
    i:Integer;
    st:string;
begin
  Randomize();
  SetLength(Arr, 5);
  st:='';
  for i := Low(Arr) to High(Arr) do
  begin
    Arr[i]:=Random(100);
    st:=st+Format('%3d',[Arr[i]]);
  end;
  Memo1.Lines.Add('ヒープソート処理前：'+st);

  //ヒープソート実行
  HeapSort(Arr);

  st:='';
  for i := Low(Arr) to High(Arr) do
    st:=st+Format('%3d',[Arr[i]]);
  Memo1.Lines.Add('ヒープソート処理後：'+st);
end;

end.

ヒープソート ～Delphiソースコード集

ヒープソートのソースコード

ヒープソート～Delphiソースコード集