Skip to content

Instantly share code, notes, and snippets.

@iskolbin
Created February 28, 2018 16:45
Show Gist options
  • Save iskolbin/0a9daa40b6b465ca49eb43f71eb34552 to your computer and use it in GitHub Desktop.
Save iskolbin/0a9daa40b6b465ca49eb43f71eb34552 to your computer and use it in GitHub Desktop.
Persistent Pairing Heap in 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment