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.

  • ‘size`: Returns the number of elements in the queue.

Example usage:

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

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Constructor Details

#initialize ⇒ PriorityQueue

Returns a new instance of PriorityQueue.



52
53
54
 
# File 'lib/ruby_priority_queue.rb', line 52

def initialize
  @heap = []
end

Instance Method Details

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


73
74
75
 
# File 'lib/ruby_priority_queue.rb', line 73

def empty?
  @heap.empty?
end

#peek ⇒ Array

Returns an array containing the item and its priority.

Returns:

  • (Array) —

    an array containing the item and its priority



78
79
80
 
# File 'lib/ruby_priority_queue.rb', line 78

def peek
  [@heap[0].item, @heap[0].priority]
end

#pop ⇒ Array

Returns an array containing the item and its priority.

Returns:

  • (Array) —

    an array containing the item and its priority



64
65
66
67
68
69
70
71
 
# File 'lib/ruby_priority_queue.rb', line 64

def pop
  return if @heap.empty?

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

#push(item = nil, priority = nil, **kwargs) ⇒ Object 



56
57
58
59
60
61
 
# File 'lib/ruby_priority_queue.rb', line 56

def push(item = nil, priority = nil, **kwargs)
  item ||= kwargs[:item]
  priority ||= kwargs[:priority]
  @heap << Node.new(item, priority)
  bubble_up(@heap.size - 1)
end

#size ⇒ Object 



82
83
84
 
# File 'lib/ruby_priority_queue.rb', line 82

def size
  @heap.size
end