Re: Priority Queue

[Gé Weijers <ge@...>]

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