Class: Ferret::Utils::PriorityQueue

Inherits:
Object
  • Object
show all
Defined in:
ext/r_utils.c

Overview

Summary

A PriorityQueue is a very useful data structure and one that needs a fast implementation. Hence this priority queue is implemented in C. It is pretty easy to use; basically you just insert elements into the queue and pop them off.

The elements are sorted with the lowest valued elements on the top of the heap, ie the first to be popped off. Elements are ordered using the less_than ‘<’ method. To change the order of the queue you can either reimplement the ‘<’ method pass a block when you initialize the queue.

You can also set the capacity of the PriorityQueue. Once you hit the capacity, the lowest values elements are automatically popped of the top of the queue as more elements are added.

Example

Here is a toy example that sorts strings by their length and has a capacity of 5;

q = PriorityQueue.new(5) {|a, b| a.size < b.size}
q << "x"
q << "xxxxx"
q << "xxx"
q << "xxxx"
q << "xxxxxx"
q << "xx" # hit capacity so "x" will be popped off the top

puts q.size     #=> 5
word = q.pop    #=> "xx"
q.top << "yyyy" # "xxxyyyy" will still be at the top of the queue
q.adjust        # move "xxxyyyy" to its correct location in queue
word = q.pop    #=> "xxxx"
word = q.pop    #=> "xxxxx"
word = q.pop    #=> "xxxxxx"
word = q.pop    #=> "xxxyyyy"
word = q.pop    #=> nil