Max Heap

--a heap is a semi organised structure, at the root it has the maximum (or minimum need to change code for that) value.
--http://en.wikipedia.org/wiki/Heap_(data_structure)
 
 
--methodes:   
--            deleteRootFromMaxHeap(heap) removes the maximum value, and returns the other values in a heap structure
--            addToMaxHeap(heap,b) adds the value b to the existing maxheap "heap"
--            TestHeap() shows how the heap works
 
--the heap is just a list in this implementation, with the max value at list[1]. a object (parent script) version could also be made .
--this Max heap can also be recoded to a Min heap by changing some + and -. 
 
--the value b can be exchanged by a [key, content] to be more usefull, where key takes the place for b and the content can be anything.
--It is a standart implementation translated to lingo from the book: Computer Algorithms, Introduction to design and Analysis.
--It is my assumption that these datastuctures are so common and old that they are in public domain. Correct me if im wrong.  
 
 
on TestHeap()
 
 
  --maak een heap aan met addToHeap()
  heap=[]
  repeat with n=1 to 20
    addToMaxHeap(heap,random(50))
  end repeat
 
  put "addHeapTest", heap
 
  repeat with n=1 to 5
 
 
    heap=deleteRootFromMaxHeap(heap)
 
  end repeat
 
  put "heap left:" , heap
 
 
end
 
on addToMaxHeap(heap,b)
  n=heap.count
  heap.addAt(n+1,b) 
  return addMaxHulp(heap, n+1, b)
 
end
 
on addMaxHulp(heap, n,b)
 
  if n = 1 then
    heap[1]=b
    return heap
  end if
 
  ParentB=(n)/2
  if heap[ParentB] < b then
    heap[n]=heap[ParentB]
    heap[ParentB]=b
    addMaxHulp(heap, ParentB , b)
 
  end if
  return heap
 
end
 
 
on deleteRootFromMaxHeap(heap)
 
  n=heap.count
  if n>1 then
    rightLeaf=heap[n]
    heap.deleteAt(n)
    return fixMaxheap(heap,heap.count,1, rightLeaf) --deleted at rightest leaf now fix heap to het the max out and the rightLeaf in
  else if n=1 then
    heap.deleteAt(1)
    return heap
  else
    return heap
    put "no heap input"
  end if
 
end
 
on fixMaxheap(heap,n,root,toBeInserted) --n=heapsize
  leftChild=2*root
  rightChild=2*root+1
 
  if (leftChild>n) then
    heap[root]=toBeInserted
  else
    if (leftChild = n) then
 
      largerSubHeap= leftChild
    else if heap[leftChild] > heap[rightChild] then
      largerSubHeap=leftChild
    else
      largerSubHeap=rightChild
    end if
 
    if (toBeInserted >= heap[largerSubHeap]) then
      heap[root]=toBeInserted
    else
      heap[root]= heap[largerSubHeap]
      return fixMaxHeap(heap, n, largerSubHeap, toBeInserted)
 
    end if
  end if
  return heap
end