Persistent Pairing Heap in Lua

pairingheap.lua

local PairingHeap = {}

function PairingHeap.make()
	return {}
end

function PairingHeap.merge( self, other )
	if not self or self[2] == nil then
		return other
	elseif not other or other[2] == nil then
		return self
	elseif self[2] >= other[2] then
		return {self[1], self[2], {other,self[3]}}
	else
		return {other[1], other[2], {self,other[3]}}
	end
end

local merge = PairingHeap.merge

function PairingHeap.enqueue( self, item, priority )
	return merge( self, {item,priority} )
end

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

local function mergepairs( subheaps )
	if not subheaps or subheaps[1] == nil then
		return nil
	else
		local car, cdr = subheaps[1], subheaps[2]
		if cdr == nil then
			return car
		else
			return merge( merge( car, cdr[1] ), mergepairs( cdr[2] ))
		end
	end
end

function PairingHeap.dequeue( self )
	if self[1] ~= nil then
		return mergepairs( self[3] )
	end
end

return PairingHeap