Class: Async::Background::MinHeap

Inherits:
Object
  • Object
show all
Defined in:
lib/async/background/min_heap.rb

Instance Method Summary collapse

Constructor Details

#initialize ⇒ MinHeap

Returns a new instance of MinHeap.



6
7
8
 
# File 'lib/async/background/min_heap.rb', line 6

def initialize
  @data = []
end

Instance Method Details

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


33
34
35
 
# File 'lib/async/background/min_heap.rb', line 33

def empty?
  @data.empty?
end

#peek ⇒ Object 



29
30
31
 
# File 'lib/async/background/min_heap.rb', line 29

def peek
  @data.first
end

#pop ⇒ Object 



15
16
17
18
19
20
21
22
 
# File 'lib/async/background/min_heap.rb', line 15

def pop
  return if @data.empty?

  swap(0, @data.size - 1)
  entry = @data.pop
  sift_down(0) unless @data.empty?
  entry
end

#push(entry) ⇒ Object 



10
11
12
13
 
# File 'lib/async/background/min_heap.rb', line 10

def push(entry)
  @data << entry
  sift_up(@data.size - 1)
end

#replace_top(entry) ⇒ Object 



24
25
26
27
 
# File 'lib/async/background/min_heap.rb', line 24

def replace_top(entry)
  @data[0] = entry
  sift_down(0)
end

#size ⇒ Object 



37
38
39
 
# File 'lib/async/background/min_heap.rb', line 37

def size
  @data.size
end