######## BINARY HEAP ######## Reference implementation: BinaryHeap = class() -- the constructor (to be called with :new()), that takes no parameters. function BinaryHeap:_init() self.entries = {} return self end -- return how many elements are there in the heap function BinaryHeap:len() return #self.entries end -- insert a new element into the binary heap, order must be non-nil and -- comparable to whatever other elements are inserted, data may be nil -- though. function BinaryHeap:insert(order, data) local entries = self.entries entries[#entries + 1] = {order = order, data = data} local p = #entries local parent = math.floor(p/2) while p > 1 and order > entries[parent].order do entries[parent], entries[p] = entries[p], entries[parent] p, parent = parent, math.floor(parent/2) end end -- remove and return the biggest element, the return value will consist -- of the order followed by its associated data. -- Do nothing if the heap is empty (no return). function BinaryHeap:pop() local entries = self.entries local entry = entries[1] entries[1] = entries[#entries] entries[#entries] = nil local p = 1 while #entries >= 2 * p do if entries[2*p+1] and entries[2*p+1].order > math.max(entries[2*p].order, entries[p].order) then entries[p], entries[2*p+1] = entries[2*p+1], entries[p] elseif entries[2*p].order > entries[p].order then entries[p], entries[2*p] = entries[2*p], entries[p] else break end end if entry then return entry.order, entry.data end end -- obtain biggest element without removing it from the heap, -- if the heap is empty, there won't be anything returned, otherwise -- the order followed by its associated data will be returned. function BinaryHeap:peek() local entry = self.entries[1] if entry then return entry.order, entry.data end end -- simple iterator that can be used with: -- for order, data in binaryheap:consume() do -- -- this will begin iteration with the biggest item -- end function BinaryHeap:consume() return function() return self:pop() end end