A binary heap is a way to quickly find the greatest or least value in an array of values.
More information in the code.
`A binary heap is a way to quickly find the greatest or least value in an array of values.
`It is much faster than simply going through the array and comparing items because the
`lowest (or highest) item is always at the top.
`The heap looks like a giant root system:
` 1
` / \
` 2 3
` / \ / \
` 4 5 6 7
`When a value is added to the heap, it is put in the last item of the Heap(0) array.
`Then, it is moved to its proper place by comparing it with the one about it.
`For more information, see this great article, where I learned about it:
` http://www.policyalmanac.org/games/binaryHeaps.htm
`The array Values(0) can be replaced with any one-dimensional array you use to store values
`in your code. Just do a Find-Replace using Values and the name of your array.
`Heap_Add(ID) will register a value in the heap. The parameter should be the value's position
`in the Values(0) array.
`Heap_Resort(ID) must be called after you have changed the value of an item to replace it where
`it needs to be. The parameter should be the value's position in the Values(0) array.
`Heap_Delete() will delete the top item from the heap. Preferably, you would use this after
`you had read that item [ Heap(1) ] and taken care of it. In some implementations, you may
`not want to use this command. Only use it if you don't want the same value to come up
`multiple times.
`Heap_Draw() is for debugging purposes and will represent the entire heap on the screen.
`=== Heap Setup ===
DIM Values(5)
DIM Heap(0)
`If 0, the lowest value will be on top
`If 1, the highest value will be on top
`Do not change this value after you have added items to the heap!
`If you need to, you must clear the heap and re-add all the items AFTER changing the direction.
global heap_dir
heap_dir=1
`=== ==== ===== ===
`Example code:
Values(1)=5
Values(2)=8
Values(3)=10
Values(4)=3
Values(5)=2
Heap_Add(1)
Heap_Add(2)
Heap_Add(3)
Heap_Add(4)
Heap_Draw()
wait key
Values(2)=22
Heap_Resort(2)
Heap_Draw()
wait key
Values(2)=2
Heap_Resort(2)
Heap_Draw()
wait key
Heap_Delete()
Heap_Draw()
wait key
end
`======= Functions ====================
function Heap_Add(ID)
array insert at bottom Heap(0)
Heap(array count(Heap(0)))=ID
temp=array count(Heap(0))
temp2=temp
while temp>1
temp=temp/2
if heap_dir=0
if Values(Heap(temp))>Values(ID)
Heap(temp2)=Heap(temp)
Heap(temp)=ID
else
exit
endif
else
if Values(Heap(temp))<Values(ID)
Heap(temp2)=Heap(temp)
Heap(temp)=ID
else
exit
endif
endif
temp2=temp
endwhile
endfunction
function Heap_Resort(ID)
for c=1 to array count(Heap(0))
if Heap(c)=ID
temp2=c
tempk=c
exit
endif
next c
temp=temp2
while temp>1
temp=temp/2
if heap_dir=0
if Values(Heap(temp))>Values(ID)
Heap(temp2)=Heap(temp)
Heap(temp)=ID
else
exit
endif
else
if Values(Heap(temp))<Values(ID)
Heap(temp2)=Heap(temp)
Heap(temp)=ID
else
exit
endif
endif
temp2=temp
endwhile
temp=tempk
temp2=temp
do
temp=temp*2
if temp>array count(Heap(0)) then exit
if heap_dir=0
if Values(Heap(temp2))>Values(Heap(temp)) then temp3=temp
else
if Values(Heap(temp2))<Values(Heap(temp)) then temp3=temp
endif
if temp+1<=array count(Heap(0))
if heap_dir=0
if Values(Heap(temp2))>Values(Heap(temp+1)) and Values(Heap(temp+1))<Values(Heap(temp)) then temp3=temp+1
else
if Values(Heap(temp2))<Values(Heap(temp+1)) and Values(Heap(temp+1))>Values(Heap(temp)) then temp3=temp+1
endif
endif
if temp3>0
tempX=Heap(temp2)
Heap(temp2)=Heap(temp3)
Heap(temp3)=tempX
else
exit
endif
temp3=0
temp2=temp
loop
endfunction
function Heap_Delete()
Heap(1)=Heap(array count(Heap(0)))
array delete element Heap(0),array count(Heap(0))
temp=1
temp2=temp
do
temp=temp*2
if temp>array count(Heap(0)) then exit
if heap_dir=0
if Values(Heap(temp2))>Values(Heap(temp)) then temp3=temp
else
if Values(Heap(temp2))<Values(Heap(temp)) then temp3=temp
endif
if temp+1<=array count(Heap(0))
if heap_dir=0
if Values(Heap(temp2))>Values(Heap(temp+1)) and Values(Heap(temp+1))<Values(Heap(temp)) then temp3=temp+1
else
if Values(Heap(temp2))<Values(Heap(temp+1)) and Values(Heap(temp+1))>Values(Heap(temp)) then temp3=temp+1
endif
endif
if temp3>0
tempX=Heap(temp2)
Heap(temp2)=Heap(temp3)
Heap(temp3)=tempX
else
exit
endif
temp3=0
temp2=temp
loop
endfunction
function Heap_Draw()
cls
width=50
height=50
Counter=0
Row=0
for c=1 to array count(Heap(0))
inc Counter
if Counter>2^Row
inc Row
Counter=1
endif
text Counter*width,Row*height,str$(Values(Heap(c)))
text Counter*width,Row*height+10,str$(Heap(c))
line Counter*width,Row*height,(c/2-(2^(Row-1)-1))*width,(Row-1)*height
next c
endfunction
