Class: RubyPriorityQueue::PriorityQueue

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

Overview

The RubyPriorityQueue module provides a simple implementation of a priority queue. A priority queue is a data structure where each element is associated with a priority, and elements are served based on their priority.

The PriorityQueue class within this module supports the following operations:

  • ‘push(item, priority)`: Adds an item with the given priority to the queue.

  • ‘pop`: Removes and returns the item with the highest priority.

  • ‘empty?`: Checks if the queue is empty.

  • ‘peek`: Returns the item with the highest priority without removing it.

Example usage:

pq = RubyPriorityQueue::PriorityQueue.new
pq.push("task1", 1)
pq.push("task2", 2)
pq.pop # => ["task1", 1]

Instance Method Summary collapse

Constructor Details

#initialize ⇒ PriorityQueue 



24
25
26
 
# File 'lib/ruby_priority_queue.rb', line 24

def initialize
  @heap = []
end

Instance Method Details

#empty? ⇒ Boolean 



42
43
44
 
# File 'lib/ruby_priority_queue.rb', line 42

def empty?
  @heap.empty?
end

#peek ⇒ Object 



46
47
48
 
# File 'lib/ruby_priority_queue.rb', line 46

def peek
  @heap[0]
end

#pop ⇒ Object 



33
34
35
36
37
38
39
40
 
# File 'lib/ruby_priority_queue.rb', line 33

def pop
  return if @heap.empty?

  swap(0, @heap.size - 1)
  min = @heap.pop
  bubble_down(0)
  min
end

#push(item, priority) ⇒ Object 



28
29
30
31
 
# File 'lib/ruby_priority_queue.rb', line 28

def push(item, priority)
  @heap << [item, priority]
  bubble_up(@heap.size - 1)
end