[ANN] Priority Queue 0.0.0.0. ... .0

ruby-talk
1

As I recently said, I'd like some more advanced datastructures in
ruby. So I wrote a nice priority queue extension. Maybe it's not so
nice c-code right now, because it is my first try on an extension, but
it works really good. I created quite a quick quiz solver with it :wink:

As I have a problem with my webspace at the moment, this first release
is mailing list only. The extension is not packaged for installation
but it is easy to build and use.

It's late here and I'm talking weird stuff, so I'll just paste the
readme and append the library.

Have fun,

Brian

priority_queue.tar.bz (7.46 KB)

priority_queue.tar.gz (9.38 KB)

路路路

--------------------------------------------------

# Ruby extension implementing a priority queue

## Description
This is a fibonacy heap priority queue implementation. That means

insert: O(1)
decrease_priority: Amortized O(1)
delete_min: Amortized O(log n)

## Legal stuff
(c) 2005 Brian Schr枚der

Please submit bugreports to priority_queue@brian-schroeder.de

This extension is under the same license as ruby.

Do not hold me reliable for anything that happens to you, your programs or
anything else because of this extension. It worked for me, but there is no
guarantee it will work for you.

## Installation
ruby extconf\.rb make

put priority_queue.so somewhere where your program can find it. E.g.
/usr/local/lib/ruby/1.8/priority_queue.so

## Usage

    require 'priority_queue'

    q = PriorityQueue.new
    q.push "node1", 0
    q.puts "node2", 1

    q.min #=> "node1"

    q.decrease_priority("node2", -1)

    q.pop_min #=> "node2"
    q.min #=> "node1"

--------------------------------------------------

--
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/

2

As I recently said, I'd like some more advanced datastructures in
ruby. So I wrote a nice priority queue extension. Maybe it's not so
nice c-code right now, because it is my first try on an extension, but
it works really good. I created quite a quick quiz solver with it :wink:

Oooh nice :wink: And a full blown Fibonacci Heap even. Thank you.

As I have a problem with my webspace at the moment, this first release
is mailing list only. The extension is not packaged for installation
but it is easy to build and use.

## Usage

    require 'priority_queue'

    q = PriorityQueue.new
    q.push "node1", 0
    q.puts "node2", 1

Why not "def push(priority, *args)"? That would make it easier to store multiple things in the queue.

   q.push distance, x, y
   [...]
   x, y = q.pop_min

    q.decrease_priority("node2", -1)

It should be possible to add things to the queue multiple times and access them separately. This would not work in the current version:

   q.push :foo, 1
   q.push :foo, 100
   q.decrease_priority :foo, 0

If you wrap everything into a new array when it is inserted into the queue the following would be possible:

   h1 = q.push 1, :foo #=> [:foo]
   h2 = q.push 100, :foo #=> [:foo]
   q.decrease_priority(0, h1)

I don't know if this is better, though

Viele Gr眉脽e,
Levin

路路路

Brian Schr枚der <ruby.brian@gmail.com> wrote:

3

[snip]
> ## Usage
>
> require 'priority_queue'
>
> q = PriorityQueue.new
> q.push "node1", 0
> q.puts "node2", 1

Why not "def push(priority, *args)"? That would make it easier to store
multiple things in the queue.

What would that mean? Create n nodes with priority priority, or create
on node with an array of n entries. I think that would be unintuitive.

   q.push distance, x, y
   [...]
   x, y = q.pop_min

> q.decrease_priority("node2", -1)

It should be possible to add things to the queue multiple times and access
them separately. This would not work in the current version:

   q.push :foo, 1
   q.push :foo, 100
   q.decrease_priority :foo, 0

If you wrap everything into a new array when it is inserted into the queue
the following would be possible:

   h1 = q.push 1, :foo #=> [:foo]
   h2 = q.push 100, :foo #=> [:foo]
   q.decrease_priority(0, h1)

I don't know if this is better, though

I could expose the nodes of the priority queue. I decided against
this, because that means that I can spare creating a ruby object for
each queue entry.
Maybe I should create two different types of queues, one with the hash
magick I'm using already and one where the user has to keep track of
the nodes himself.

Viele Gr眉脽e,
Levin

Danke,

Brian

路路路

On 30/08/05, Levin Alexander <levin@grundeis.net> wrote:

--
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/