Class: DS::PriorityQueue

Inherits:
Queue
  • Object
show all
Defined in:
lib/ds/queues/priority_queue.rb

Instance Method Summary collapse

Methods inherited from Queue

create, #empty?, #length

Constructor Details

#initialize ⇒ PriorityQueue

Create new priority queue. Internaly uses heap to store elements.



5
6
7
 
# File 'lib/ds/queues/priority_queue.rb', line 5

def initialize
  @store = BinaryHeap.new {|parent,child| parent.key >= child.key}
end

Instance Method Details

#dequeue ⇒ Object Also known as: shift

Removes element with highest priority from queue .



20
21
22
23
24
25
26
 
# File 'lib/ds/queues/priority_queue.rb', line 20

def dequeue
  if x = @store.shift
    x.value
  else
    x
  end
end

#enqueue(x, priority) ⇒ Object Also known as: push

Adds element to queue with given priority.



11
12
13
14
15
 
# File 'lib/ds/queues/priority_queue.rb', line 11

def enqueue x, priority
  pair = Pair.new(priority,x)
  @store.insert(pair)
  self
end

#peek ⇒ Object

Returns element with highest priority.



31
32
33
 
# File 'lib/ds/queues/priority_queue.rb', line 31

def peek
  @store.data.first.value
end