Class: DS::PriorityQueue

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

Overview

Class implements Priority Queue

Instance Method Summary collapse

Constructor Details

#initialize(*args) ⇒ PriorityQueue

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



5
6
7
8
9
10
11
12
13
 
# File 'lib/ds/queues/priority_queue.rb', line 5

def initialize(*args)
  @store = if block_given?
             BinaryHeap.new(*args) do |parent, child|
               yield parent.key, child.key
             end
           else
             BinaryHeap.new(*args) { |parent, child| parent.key >= child.key }
           end
end

Instance Method Details

#dequeue ⇒ Object Also known as: shift

Removes element with highest priority from queue.



25
26
27
28
 
# File 'lib/ds/queues/priority_queue.rb', line 25

def dequeue
  x = @store.shift
  x ? x.value : nil
end

#empty? ⇒ Boolean

Checks if queue is empty.

Returns:

  • (Boolean) 


45
46
47
 
# File 'lib/ds/queues/priority_queue.rb', line 45

def empty?
  @store.empty?
end

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

Adds element to queue with given priority.



16
17
18
19
20
 
# File 'lib/ds/queues/priority_queue.rb', line 16

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

#length ⇒ Object Also known as: size

Returns length of queue. If queue is empty returns 0.



38
39
40
 
# File 'lib/ds/queues/priority_queue.rb', line 38

def length
  @store.length
end

#peek ⇒ Object

Returns element with highest priority.



33
34
35
 
# File 'lib/ds/queues/priority_queue.rb', line 33

def peek
  @store.top.value
end