```|Portada|Blog|Wiki|
```
```######## 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

```
```document.title="wiki: lua/binary-heap"
```