Class: Pathfinding::PriorityQueue

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

Overview

A Priority Queue implementation for managing elements with associated priorities. Elements are stored and retrieved based on their priority values.

This Priority Queue is implemented using a binary heap, which provides efficient insertion, extraction of the minimum element, and deletion operations.

Instance Method Summary collapse

Constructor Details

#initialize(&block) ⇒ PriorityQueue

Returns a new instance of PriorityQueue.



12
13
14
15
16
 
# File 'lib/pathfinding/priority_queue.rb', line 12

def initialize(&block)
  @heap = []
  @compare = block || proc { |a, b| @priority_hash[a] < @priority_hash[b] }
  @priority_hash = {}
end

Instance Method Details

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


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

def empty?
  @heap.empty?
end

#peek ⇒ Object 



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

def peek
  @heap[0]
end

#pop ⇒ Object 



24
25
26
27
28
29
30
31
 
# File 'lib/pathfinding/priority_queue.rb', line 24

def pop
  return nil if @heap.empty?

  swap(0, @heap.length - 1)
  popped = @heap.pop
  heapify_down(0)
  popped
end

#push(item, priority) ⇒ Object 



18
19
20
21
22
 
# File 'lib/pathfinding/priority_queue.rb', line 18

def push(item, priority)
  @heap << item
  @priority_hash[item] = priority
  heapify_up(@heap.length - 1)
end