pQueue.lua

local function sift_up(queue, index)
	local current, parent = index, (index - (index % 2))/2
	while current > 1 and queue.cmp(queue[current][2], queue[parent][2]) do
		queue[current], queue[parent] = queue[parent], queue[current]
		current, parent = parent, (parent - (parent % 2))/2
	end
	return current
end

local function sift_down(queue, index)
	local current, child, size = index, 2*index, #queue
	while child <= size do
		if child < size and queue.cmp(queue[child + 1][2], queue[child][2]) then
			child = child + 1
		end
		if queue.cmp(queue[child][2], queue[current][2]) then
			queue[current], queue[child] = queue[child], queue[current]
			current, child = child, 2*child
		else
			break
		end
	end
	return current
end

local methods = {

	insert = function(self, element, value)
		table.insert(self, {element, value})
		return sift_up(self, #self)
	end,

	remove = function(self, element, compFunc)
		local index = self:contains(element, compFunc)
		if index then
			local size = #self
			self[index], self[size] = self[size], self[index]
			local ret = table.remove(self)
			if size > 1 and index < size then
				sift_down(self, index)
				if index > 1 then
					sift_up(self, index)
				end
			end
			return unpack(ret)
		end
	end,

	pop = function(self)
		if self[1] then
			local size = #self
			self[1], self[size] = self[size], self[1]
			local ret = table.remove(self)
			if size > 1 then
				sift_down(self, 1)
			end
			return unpack(ret)
		end
	end,

	peek = function(self)
		if self[1] then
			return self[1][1], self[1][2]
		end
	end,

	contains = function(self, element, compFunc)
		for index, entry in ipairs(self) do
			if (compFunc and compFunc(entry[1], element)) or entry[1] == element then
				return index
			end
		end
		return false
	end,

	isEmpty = function(self)
		return #self == 0
	end,

	size = function(self)
		return #self
	end,

	getValue = function(self, element, compFunc)
		local index = self:contains(element, compFunc)
		return (index and self[index][2]) or false
	end,

	setValue = function(self, element, value, compFunc)
		local index = self:contains(element, compFunc)
		if index then
			self[index][2] = value
			sift_up(self, index)
			sift_down(self, index)
			return true
		else
			return false
		end
	end,

}

function new(compareFunc)
	local queue = {}
	queue.cmp = type(compareFunc) == "function" and compareFunc or function(a, b) return a < b end
	setmetatable(queue, {__index = methods})
	return queue
end