Build Heap And Heapsort Without Array

[DGL-luke]

A heap can be very easily organized into an array, but if you use binary heaps, this type should be able to help you:

Delphi-Quellcode:

type 
  PHeapNode = ^THeapNode;
  THeapNode = record
    Parent,Left,Right: PHeapNode;
    Value: Integer;
  end;

With this you should be able to build a heap:

Delphi-Quellcode:

function RandomHeap(depth: Integer; BaseNode: PHeapNode = nil): THeapNode
var i: Integer;
begin
if (BaseNode = nil) then
  begin
    Result := New(THeapNode)
  end
else
  begin
    Result := BaseNode;
    Result.Value := random(100);
  end;

if depth > 0 then
  begin
    Result.Left := New(THeapNode);
    Result.Left.Parent := BaseNode;
    ReandomHeap(depth-1,Result.Left);
   
    Result.Right := New(THeapNode);
    Result.Left.Parent := BaseNode;
    RandomHeap(depth-1,Result.Right);
  end;
end;

procedure MaxSort(Heap: THeapNode);
begin
// too lazy to write that now xD
end;

maybe I left out some pointer conversions, but that should be it.
And don't forget to free all memory you assign!
(When you make the record a class, you can implement this in the class)