Class: DS::PriorityQueue

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

Overview

Class implements Priority Queue

Direct Known Subclasses

IndexedPriorityQueue

Class Method Summary collapse

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

Class Method Details

.min(*args) ⇒ Object 



15
16
17
 
# File 'lib/ds/queues/priority_queue.rb', line 15

def self.min(*args)
  new(*args) { |parent, child| parent < child }
end

Instance Method Details

#dequeue ⇒ Object Also known as: shift

Removes element with highest priority from queue.



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

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

#empty? ⇒ Boolean

Checks if queue is empty.

Returns:

  • (Boolean) 


49
50
51
 
# File 'lib/ds/queues/priority_queue.rb', line 49

def empty?
  @store.empty?
end

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

Adds element to queue with given priority.



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

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.



42
43
44
 
# File 'lib/ds/queues/priority_queue.rb', line 42

def length
  @store.length
end

#peek ⇒ Object

Returns element with highest priority.



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

def peek
  @store.top.value
end