Class: MapReduce::PriorityQueue

Inherits:
Object
  • Object
show all
Defined in:
lib/map_reduce/priority_queue.rb

Overview

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

Instance Method Summary collapse

Constructor Details

#initialize ⇒ PriorityQueue

Initializes the priority queue.

Examples:

MapReduce::PriorityQueue.new


33
34
35
36
 
# File 'lib/map_reduce/priority_queue.rb', line 33

def initialize
  @queue = MinPriorityQueue.new
  @sequence_number = 0
end

Instance Method Details

#pop ⇒ Object

Pops the min item from the queue.

Examples:

priority_queue = MapReduce::PriorityQueue.new
priority_queue.push("object1", "key1")
priority_queue.push("object2", "key2")
priority_queue.pop


65
66
67
68
69
 
# File 'lib/map_reduce/priority_queue.rb', line 65

def pop
  _, object = @queue.pop

  object
end

#push(object, key) ⇒ Object

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.

Examples:

priority_queue = MapReduce::PriorityQueue.new
priority_queue.push("some object", "some key")

Parameters:

  • object —

    The object to add to the priority queue.

  • key —

    The key to use for sorting.



49
50
51
52
53
 
# File 'lib/map_reduce/priority_queue.rb', line 49

def push(object, key)
  @queue.push([@sequence_number, object], SortKey.new(key))

  @sequence_number += 1
end