minheap implemented by using lua table(array). Tested pass with luajit.

minheap.lua

--[[ Copyright (C) urey-hiker (ureydev # aliyun.com)

usage:
local minheap = require("minheap")
local heap = minheap.new()
-- push an obj and ordered by ID in the heap
heap:push(ID, obj)
-- pop out the obj with the min ID
ID, obj = heap:pop()
-- peek the min obj and ID
ID, obj = heap:peek()
]]

local tbl_insert = table.insert
local tbl_remove = table.remove

local _M = {}

local function _less(a, b)
    return a < b
end

local mt = {__index = _M}


function _M.new(less)
    if less ~= nil then
        return setmetatable({}, {__index = setmetatable({less = less}, mt)})
    end
    return setmetatable({}, {__index = setmetatable({less = _less}, mt)})
end

local function up(self, bt)
    local up
    local less = self.less
    up = math.floor(bt / 2)
    while up > 0 do
        if less(self[bt]._id, self[up]._id) then
            self[bt], self[up] = self[up], self[bt]
        else
            break
        end
        bt = up
        up = math.floor(bt / 2)
    end
end

local function down(self, up)
    local nt, bt
    local less = self.less
    bt = #self + 1
    nt = up * 2
    while nt < bt do
        if nt + 1 < bt and less(self[nt + 1]._id, self[nt]._id) then
            nt = nt + 1
        end
        if less(self[nt]._id, self[up]._id) then
            self[nt], self[up] = self[up], self[nt]
            up = nt
            nt = up * 2
        else
            return
        end
    end
end

function _M.push(self, id, obj)
    local tmp = {['_id'] = id, ['obj'] = obj}
    local bt
    bt = #self + 1
    tbl_insert(self, bt, tmp)
    up(self, bt)
end

function _M.pop(self)
    local up, bt, ret
    bt = #self
    if bt == 0 then
        return nil, nil
    end
    if bt < 3 then
        ret = self[1]
        tbl_remove(self, 1)
        return ret._id, ret.obj
    end
    ret = self[1]
    self[1] = self[bt]
    tbl_remove(self, bt)
    down(self, 1)
    return ret._id, ret.obj
end

function _M.peek(self)
    local ret = self[1]
    if ret == nil then
        return nil, nil
    end
    return ret._id, ret.obj
end

function _M.clone(self)
	local newHeap = _M.new(self.less)
	for i = 1, #self do
		tbl_insert(newHeap, self[i])
	end
	return newHeap
end

return _M