Just getting my toe in the water ...
-- heap.lua -- implementation of min binary heap for use as a priority queue
function HeapAdd( heap , newKey, newValue ) -- adds or creates a new heap
if heap == nil then -- if the heap is empty create a new one
heap = { key = newKey, value = newValue } -- add this node as root
return heap -- return the new heap
else
if newKey < heap.key then -- if less, recursively add to left node
return HeapAdd( heap.left , newKey, newValue )
else -- otherwise, add to right node
return HeapAdd( heap.right, newKey, newValue )
end
end
end
function HeapMin( heap , key) -- returns the node with the smallest key
if heap == nil then -- if the heap is empty, return nil
return nil
else if heap.left ~= nil then -- recursively traverse down the left
return HeapPeek( heap.left, key )
else -- if no left branch is found, the node will be the smallest value
return heap
end
end
function HeapPeek( heap , key ) -- returns the next value without removing it
local min = HeapMin ( heap , key )
return min.value
end
function HeapNext( heap , key )-- returns the next value after removing it from the heap
local min = HeapMin ( heap , key )
local minValue = min.value
if min.right == nil -- check to see if the minimum node has children
min = nil -- if so, remove the node
else -- otherwise, replace the minimum node with the node in it's right branch
min = min.right
end
return minValue -- return the minimum value
end