wiki: lua/binary-heap

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



                                                                              π