Class: Lich::Common::MinHeap

Inherits:
Object
  • Object
show all
Defined in:
documented/common/map/map_base.rb

Overview

MinHeap for efficient Dijkstra priority queue Extracted to be shared across all game implementations

Instance Method Summary collapse

Constructor Details

#initialize ⇒ void

Initializes an empty binary min-heap.



25
26
27
 
# File 'documented/common/map/map_base.rb', line 25

def initialize
  @heap = []
end

Instance Method Details

#empty? ⇒ Boolean

Checks whether the heap holds any elements.

Returns:

  • (Boolean) —

    true if the heap is empty



57
58
59
 
# File 'documented/common/map/map_base.rb', line 57

def empty?
  @heap.empty?
end

#pop ⇒ [Numeric, Object]?

Removes and returns the minimum-priority element.

Returns:

  • ([Numeric, Object], nil) —

    a [priority, value] pair, or nil if empty



45
46
47
48
49
50
51
52
 
# File 'documented/common/map/map_base.rb', line 45

def pop
  return nil if @heap.empty?

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

#push(priority, value) ⇒ void

This method returns an undefined value.

Adds an element to the heap with the given priority.

Lower priority values bubble toward the root. Maintains heap invariant after insertion.

Parameters:

  • priority (Numeric) —

    the sort key for this element

  • value (Object) —

    the value to store



37
38
39
40
 
# File 'documented/common/map/map_base.rb', line 37

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