I made this for an A* thing I've finally got working, so I thought I'd share this with everyone.
Binary heaps are a very fast way to sort things if the only part you need to be sorted is the item with the lowest value (or highest).
Here's the tutorial I learned the concept from:
(link)
Here's the code:
// by AurumKnight
// to retrieve the lowest index value and it's tag (respectively) use:
// bank dword([bank number],8)
// bank dword([bank number],12)
function bhMakeHeap(MaxIndexes)
b = find free bank()
make bank b,8+MaxIndexes*8
write bank dword b,4,maxindexes
endfunction b
`most of the time you would use 0 for 'ind'
function bhRemove(bank,ind)
hi as dword `highest index
hiv as dword `highest index value
iv1 as dword
iv2 as dword
hI = bank dword(bank,0)-1
if ind > hi then exitfunction
write bank dword bank,0,hI
hiv = bank dword(bank,8+hI*8)
hi=hi-1
ci = ind+1 `we need to be able to multiply this number
for dummy = 0 to 1 step 0
if ci*2+1-1 <= hi
iv1 = bank dword(bank,8+(ci*2-1)*8)
iv2 = bank dword(bank,8+(ci*2+1-1)*8)
if iv2 < iv1
if hiv <= iv2
exit
else
copy bank bank,8+(ci*2+1-1)*8,8,bank,8+(ci-1)*8
ci=ci*2+1
endif
else
if hiv <= iv1
exit
else
copy bank bank,8+(ci*2-1)*8,8,bank,8+(ci-1)*8
ci=ci*2
endif
endif
else
`if only one index exits, this checks it.
if ci*2-1 <= hi
if hiv <= bank dword(bank,8+(ci-1)*8*2)
exit
else
copy bank bank,8+(ci*2-1)*8,8,bank,8+(ci-1)*8
ci=ci*2
endif
else
exit
endif
endif
next dummy
copy bank bank,8+(hi+1)*8,8,bank,8+(ci-1)*8
endfunction
function bhAdd(bank,value as dword,tag as dword)
bd as dword
hi as dword `highest index
ci as dword `current index
hI = bank dword(bank,0)
ci=hi+1
while ci > 1
bd = bank dword(bank,8+(ci/2-1)*8)
if value <= bd
copy bank bank,8+(ci/2-1)*8,8,bank,8+(ci-1)*8,
ci=ci/2
else
exit
endif
endwhile
write bank dword bank,8+(ci-1)*8,value
write bank dword bank,12+(ci-1)*8,tag
write bank dword bank,0,hi+1
endfunction
`the index to be resorted must be lower than before.
function bhResort(bank,ind) `index
bd as dword
hi as dword `highest index
ci as dword `current index
value as dword
tag as dword
value = bank dword(bank,8+ind*8)
tag = bank dword(bank,12+ind*8)
ci=ind+1
while ci > 1
bd = bank dword(bank,8+(ci/2-1)*8)
if value <= bd
copy bank bank,8+(ci/2-1)*8,8,bank,8+(ci-1)*8
ci=ci/2
else
exit
endif
endwhile
write bank dword bank,8+(ci-1)*8,value
write bank dword bank,12+(ci-1)*8,tag
endfunction
`find the first index with the desired tag
function bhFindTag(bank,tag as dword)
hi as dword
hI = bank dword(bank,0)-1
if hI = -1 then exitfunction -1
for i = 0 to hi
if bank dword(bank,12+i*8)=tag then exitfunction i
next i
endfunction -1
What I store in the 'tag' is an index to an array (which has more data). If you ever want to lower a value, you have to resort it using the function 'bhResort'. Use the function 'bhFindTag' to find an index with a particular tag.
'Resort' doesn't work if you raise the value of an index (this was made with A* in mind) If anyone cares to have a version of this that works the other way (the option of putting the highest value at the top), feel free to ask me to do it. This can be really confusing to edit since it uses memory banks.
It probably wouldn't be too hard to change this to use with memblocks fyi.
Enjoy.
