Class: Lich::Common::MinHeap

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

Overview

A minimum heap implementation.

This class provides methods to manage a priority queue where the smallest element is always at the top.

Instance Method Summary collapse

Constructor Details

#initialize ⇒ MinHeap

Returns a new instance of MinHeap.



11
12
13
 
# File 'documented/common/map/map_base.rb', line 11

def initialize
  @heap = []
end

Instance Method Details

#empty? ⇒ Boolean

Checks if the heap is empty.

Returns:

  • (Boolean) —

    true if the heap is empty, false otherwise



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

def empty?
  @heap.empty?
end

#pop ⇒ Array<Object>?

Removes and returns the smallest value from the heap.

Returns:

  • (Array<Object>, nil) —

    the smallest value and its priority, or nil if the heap is empty



26
27
28
29
30
31
32
33
 
# File 'documented/common/map/map_base.rb', line 26

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 a value with a given priority to the heap.

Parameters:

  • priority (Integer) —

    the priority of the value to be added

  • value (Object) —

    the value to be added to the heap



19
20
21
22
 
# File 'documented/common/map/map_base.rb', line 19

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