Class: DSA::PriorityQueue

Inherits:
Object
  • Object
show all
Defined in:
lib/dsa-ruby/priority_queue.rb

Overview

DSA::PriorityQueue - A priority queue data structure.

Uses a heap internally to provide efficient priority-based ordering. Supports both min and max priority ordering.

Examples:

Min Priority Queue (default)

pq = DSA::PriorityQueue.new(type: :min)
pq.push("task_a", 3)
pq.push("task_b", 1)
pq.push("task_c", 2)
pq.pop  # => "task_b" (lowest priority value first)

Max Priority Queue

pq = DSA::PriorityQueue.new(type: :max)
pq.push("task_a", 3)
pq.push("task_b", 1)
pq.pop  # => "task_a" (highest priority value first)

Instance Method Summary collapse

Constructor Details

#initialize(type: :min) ⇒ DSA::PriorityQueue

Initialize a new priority queue.

Examples:

DSA::PriorityQueue.new          # min priority queue
DSA::PriorityQueue.new(type: :max)  # max priority queue

Parameters:

  • type (Symbol) (defaults to: :min) —

    :min for minimum priority first, :max for maximum priority first



26
27
28
 
# File 'lib/dsa-ruby/priority_queue.rb', line 26

def initialize(type: :min)
  @heap = type == :min ? MinHeap.new : MaxHeap.new
end

Instance Method Details

#empty? ⇒ Boolean

Checks if the priority queue is empty.

Examples:

pq = DSA::PriorityQueue.new
pq.empty?  # => true

Returns:

  • (Boolean) —

    true if the priority queue contains no items



100
101
102
 
# File 'lib/dsa-ruby/priority_queue.rb', line 100

def empty?
  @heap.empty?
end

#peek ⇒ Object

Returns the item with the highest/lowest priority without removing it.

Examples:

pq.push("task_a", 3)
pq.push("task_b", 1)
pq.peek  # => "task_b"

Returns:

  • (Object) —

    the item with the highest priority (max) or lowest (min)

Raises:

  • (IndexError) —

    if the priority queue is empty



66
67
68
69
70
 
# File 'lib/dsa-ruby/priority_queue.rb', line 66

def peek
  raise IndexError, "priority queue is empty" if empty?
  _, _, item = @heap.peek
  item
end

#pop ⇒ Object

Removes and returns the item with the highest/lowest priority.

Examples:

pq.push("task_a", 3)
pq.push("task_b", 1)
pq.pop  # => "task_b"

Returns:

  • (Object) —

    the item with the highest priority (max) or lowest (min)

Raises:

  • (IndexError) —

    if the priority queue is empty



52
53
54
55
56
 
# File 'lib/dsa-ruby/priority_queue.rb', line 52

def pop
  raise IndexError, "priority queue is empty" if empty?
  _, _, item = @heap.pop
  item
end

#priority_peek ⇒ Comparable

Returns the priority value of the top item without removing it.

Examples:

pq.push("task", 5)
pq.priority_peek  # => 5

Returns:

  • (Comparable) —

    the priority value of the top item

Raises:

  • (IndexError) —

    if the priority queue is empty



79
80
81
82
 
# File 'lib/dsa-ruby/priority_queue.rb', line 79

def priority_peek
  raise IndexError, "priority queue is empty" if empty?
  @heap.peek[0]
end

#push(item, priority) ⇒ DSA::PriorityQueue

Inserts an item with a given priority.

Examples:

pq.push("task", 5).push("another", 3)

Parameters:

  • item (Object) —

    the item to insert

  • priority (Comparable) —

    the priority value (lower = higher priority in min queue)

Returns:



37
38
39
40
41
42
 
# File 'lib/dsa-ruby/priority_queue.rb', line 37

def push(item, priority)
  @counter ||= 0
  @heap.push([priority, @counter, item])
  @counter += 1
  self
end

#size ⇒ Integer

Returns the number of items in the priority queue.

Examples:

pq.push("task_a", 3).push("task_b", 1)
pq.size  # => 2

Returns:

  • (Integer) —

    the number of items



90
91
92
 
# File 'lib/dsa-ruby/priority_queue.rb', line 90

def size
  @heap.size
end