  lua-l archive

• 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

```