Chaosforge Forum

General => Off Topic => Topic started by: C4Cypher on November 26, 2010, 13:00

Title: A priority queue heap in lua
Post by: C4Cypher on November 26, 2010, 13:00

Just getting my toe in the water ...

Code: [Select]

-- 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