Wikia

Delphi Programming

Heapsort

2,918pages on
this wiki
Talk3

procedure ButtomUpHeapsort(var Data: array of integer);

   procedure Sink(Index, Arraylength: integer);
   var
      item, leftChild, sinkIndex, rightChild, parent: integer;
      done: boolean;
   begin
      sinkIndex := index;
      item := Data[index];
      done := False;

      while not done do begin // search sink-path and move up all items
         leftChild := ((sinkIndex) * 2) + 1;
         rightChild := ((sinkIndex + 1) * 2);

         if rightChild <= Arraylength then begin
            if Data[leftChild] < Data[rightChild] then begin
               Data[sinkIndex] := Data[rightChild];
               sinkIndex := rightChild;
            end
            else begin
               Data[sinkIndex] := Data[leftChild];
               sinkIndex := leftChild;
            end;
         end
         else begin
            done := True;

            if leftChild <= Arraylength then begin
               Data[sinkIndex] := Data[leftChild];
               sinkIndex := leftChild;
            end;
         end;
      end;

      // move up current Item
      Data[sinkIndex] := item;
      done := False;

      while not done do begin
         parent := Trunc((sinkIndex - 1) / 2);
         if (Data[parent] < Data[sinkIndex]) and (parent >= Index) then begin
            item := Data[parent];
            Data[parent] := Data[sinkIndex];
            Data[sinkIndex] := item;
            sinkIndex := parent;
         end
         else
            done := True;
      end;
   end;

var
   x, b: integer;
begin
   // first make it a Heap
   for x := Trunc((High(Data) - 1) / 2) downto Low(Data) do
      sink(x, High(Data));

   // do the ButtomUpHeap sort
   for x := High(Data) downto Low(Data) + 1 do begin
      b := Data[x];
      Data[x] := Data[Low(Data)];
      Data[Low(Data)] := b;
      sink(Low(Data), x - 1);
   end;
end;

Code Snippets
DatabasesFiles and I/OForms/WindowsGraphicsNetworkingMath and AlgorithmsMiscellaneousMultimediaSystemVCL

Around Wikia's network

Random Wiki