class MapReduce::PriorityQueue

The MapReduce::PriorityQueue implements a min priority queue using a binomial heap.

Public Class Methods

new() click to toggle source

Initializes the priority queue.

@example

MapReduce::PriorityQueue.new
# File lib/map_reduce/priority_queue.rb, line 11
def initialize
  @queue = MinPriorityQueue.new
  @sequence_number = 0
end

Public Instance Methods

pop() click to toggle source

Pops the min item from the queue.

@returns The popped object.

@example

priority_queue = MapReduce::PriorityQueue.new
priority_queue.push("object1", "key1")
priority_queue.push("object2", "key2")
priority_queue.pop
# File lib/map_reduce/priority_queue.rb, line 43
def pop
  _, object = @queue.pop

  object
end
push(object, key) click to toggle source

Adds a new item to the priority queue while the key is used for sorting. The object and key can basically be everything, but the key must be some comparable object.

@param object The object to add to the priority queue. @param key The key to use for sorting.

@example

priority_queue = MapReduce::PriorityQueue.new
priority_queue.push("some object", "some key")
# File lib/map_reduce/priority_queue.rb, line 27
def push(object, key)
  @queue.push([@sequence_number, object], key)

  @sequence_number += 1
end