Build Heap And Heapsort Without Array

[sk.Silvia]

hi there i would like to know how to build a heap and heapsort without using an array (i found many alghortims, but they are all using array representation of heap)

thanks:)

[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)

[sk.Silvia]

you are 17? nice:)

hmm. your alghoritm is nice, but cause of random(100) it wont produce a heap (child can have higher value then parent)

but ok, lets say i have a binar tree and will rebuild it to a heap, what then?

[DGL-luke]

i didn't say it produced a sorted heap, which in your case would be a MAX-Heap, right? ;)

well, isn't a binary tree just about the same thing? You're right, I'm just 17, and I only took a glance at wikipedia to get the structure of a binary heap.

The rest is merely pointer acrobatics...

Just looked at wikipedia again... "a heap is an abstract data structure, mostly based on trees" (rough translation ;) )

So what does your tree look like? Is it just unsorted?

EDIT: btw, the "too lazy to write that now" comment above should not suggest that i understand heapsorting in any way (well, it does, but honestly I don't know - well, wikipedia educates) ;)

EDIT: OK, I think I got it about now - we need a heap that maintains its (existing) order so we can just pick out the biggest element one after the other.

EDIT: and yes, there are sources saying a heap is a binary tree which is sorted.

As I just feel like it, I'll outline a simple heap class based on THeapNode. Stand By ;)

EDIT: Well, I'll try ;) it's not that easy. But it should be rather easy to make a (balanced, sort of) binary tree into a sorted heap. Just take the lowest leaf and check if its value is less than its parent's value. if it is, check the next leaf. if it is not, swap them.

[tigerman33]

Hi,

if you already have a binary tree, you should be able to transform it into a heap by successively performing a so-called sift operation on the nodes from the bottom up. A sift operation means exchanging the given node with the tree root. Then if necessary, you exchange that node with the larger one of its two sons to keep the ordering. After that, recursively repeat on the just-changed subtree, until the node is at its correct position.
If I remember right, it should actually be enough to do this on only the bottom half of the tree, but I'm not going to give you any guarantuee on that one... :stupid:

I would suspect Wikipedia has an article on this operation, given that there seems to be one on the heapsort algorithm itself.

Hope this helped. :)

[tigerman33]

Wikipedia article explaining heapsort/sift:

Zitat:

Zitat von Wikipedia

Code:

function sift(a, start, count) {
     var int root := start, child

     while root * 2 + 1 < count { 
         child := root * 2 + 1 // Ignore this--you can access a node's children much easier! :)

         if child < count - 1 and a[child] < a[child + 1] // Choose the larger of the sons, if there are two

             child := child + 1

         if a[root] < a[child] // If root node is too small...
             swap(a[root], a[child]) // Swap it with the previously determined larger son
             root := child // ...and keep track of where it is now. 
               // This way, on the next loop iteration the subtree that has the just-moved node as its root will be sifted into
               // Another possible way here would have been to use recursion 
         else
             return
     }
 }

PS: Yeah, I know this isn't really C-code. Just wanted the syntax highlighting... :)

[sk.Silvia]

so ok, i have this code :

Delphi-Quellcode:

  procedure TBinTree.BuildHeap;
      begin
      if not(Left=nil) then
        begin
        if Left.Value>Value then
          begin
          Exchange(Left,Self);
          BuildHeap;
          end;
        Left.BuildHeap;
        end;
      if not(Right=nil) then
        begin
        if Right.Value>Value then
          begin   
          Exchange(Right,Self);
          BuildHeap;
          end;
        Right.BuildHeap;
        end;
      end;

it works fine, but only just with one bug, it exchanges bad the values by the tree root (it dont makes just one exchange, the rest of the tree is ok)

somebody has an idea how to fix it?

[tigerman33]

Hi Silvia,

I'm not sure if this will solve your problem, but if I read your code right you neglect to determine which one is the larger of the child nodes before you swap with the root. That might look something like this:

Delphi-Quellcode:

procedure TBinTree.BuildHeap;
var Larger: TBinTree;
begin
  // Lazy evaluation of boolean expressions needs to be switched on for this to work
  Larger := Left;
  if not Assigned(Larger) then 
    Larger := Right else
    if Assigned(Right) and (Left.Value < Right.Value) then 
      LargerSon := Right;

  if Assigned(Larger) and (Value < Larger.Value) then begin
    Exchange(Larger,self);
    Larger.BuildHeap;
  end;
end;

If that doesn't do it, we'll need to look again.

[sk.Silvia]

thanks for helping

aoup it actualy dont work right...

but when i cal my method 2 times after itself, like :
BinTree.BuildHeap;
BinTree.BuildHeap;

it makes a good heap

its not neccessary to call it more times, cause the heap is created and the output will be the same

but thats not the right way:/, it dont handle good the main root point:(