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

(Brian Schr枚der) #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/

(Levin Alexander) #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:

(Brian Schr枚der) #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/