[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
**Subject**: **Re: Priority Queue**
**From**: Gé Weijers <ge@...>
**Date**: Sun, 18 Nov 2007 09:18:30 -0800

I've found that 'skew heaps' are fairly simple to implement. See
http://en.wikipedia.org/wiki/Skew_heap

`for an explanation. The meld operation is fairly simple, a recursive
``implementation looks like this:
`
local function rmeld(a, b)
if not (a and b) then
return a or b
end
if a.key < b.key then
a.left, a.right = a.right, rmeld(a.left, b)
return a
else
b.left, b.right = b.right, rmeld(a, b.left)
return b
end
end
To create a queue:
local queue = nil
To add an element to the queue:
queue = rmeld(queue, {key = mykey})
To remove an element from the queue:
queue = rmeld(queue.left, queue.right)
Here's an iterative version of the meld operation:
local function meld(a, b)
if not (a and b) then
return a or b
end
if a.key > b.key then
a, b = b, a
end
local ret, r = a, a
a, a.left = a.left, a.right
while a ~= nil do
if a.key > b.key then
a, b = b, a
end
r.right, r = a, a
a, a.left = a.left, a.right
end
r.right = b
return ret
end
Gé
On Nov 17, 2007, at 11:53 AM, W. C. Bubel wrote:

Aside from using next or pairs and facing a O(n) complexity, are there
any other Lua ways of implementing a priority queue? About the only
way I could figure out myself was to use binary searching and
table.insert and table.remove.

--
Gé Weijers
ge@weijers.org