Example of the Heap system used in the A* pathfinding routine

Heaps are a quick and easy way to organise data to allow you to retrieve that data in sequence without keeping the data completely sorted.

You can find a description of how a heap is arranged and modified here :
http://webpub.alleg.edu/student/g/groganb/heap_text.html

There is a difference though ... I have reversed mine so that the lowest value is held at the top of the tree.

                                    ` This code was downloaded from The Game Creators
                                    ` It is reproduced here with full permission
                                    ` http://www.thegamecreators.com
                                    
                                    ` Example of using a heap.

` This example just add items to the heap and then removes them.
` This also shows that heaps retain relative ordering (ie two items
`  with a sort value of 5 are added, and are removed in the same
`  sequence)

` You will find a version of the heap algorithm at the heart of my
` A* search code, ensuring that shortest paths are checked first.

type HeapStore
   SortOrder as integer
   StoredValue as integer
endtype

global dim Heap(0) as HeapStore
global HeapSize=0

Insert(10,0)
Insert( 5,1)
Insert(15,2)
Insert( 7,3)
Insert(43,4)
Insert( 1,5)
Insert( 5,6)

PrintHeap()
print "Additions done"
print

while not Empty()
   print Heap(0).SortOrder; " - "; Heap(0).StoredValue
   Delete()
endwhile

PrintHeap()
print "Deletion done"

wait key
end


function PrintHeap()
   for i=0 to HeapSize-1
      print Heap(i).SortOrder; " - "; Heap(i).StoredValue
   next i
endfunction


function Insert(SortOrder as integer, StoredValue as integer)
   local Parent as integer
   local Child as integer

   Child=HeapSize
   inc HeapSize

   if array count( Heap() ) <= Child then array insert at bottom Heap(), (HeapSize/2)+1

   do
      if Child <= 0 then exit

      Parent=(Child - 1)/2

      if Heap(Parent).SortOrder < SortOrder then exit

      Heap(Child) = Heap(Parent)
      Child = Parent
   loop

   Heap(Child).SortOrder = SortOrder
   Heap(Child).StoredValue = StoredValue
endfunction


function Delete()
   if HeapSize <= 0 then exitfunction

   dec HeapSize
   SortOrder=Heap(HeapSize).SortOrder
   StoredValue=Heap(HeapSize).StoredValue

   Parent=0

   do
      Child=(2 * Parent)+1
      if Child >= HeapSize then exit

      if Child+1 < HeapSize then if Heap(Child).SortOrder > Heap(Child+1).SortOrder then inc Child

      if Heap(Child).SortOrder < SortOrder
         Heap(Parent) = Heap(Child)
         Parent = Child
      else
         exit
      endif
   loop

   Heap(Parent).SortOrder = SortOrder
   Heap(Parent).StoredValue = StoredValue
endfunction


function Empty()
   if HeapSize <= 0 then exitfunction 1
endfunction 0


function Size()
   exitfunction HeapSize
endfunction 0