Class: Priorityq::Heap

Inherits:
Object
  • Object
show all
Defined in:
lib/priorityq/heap.rb

Direct Known Subclasses

MinHeap

Defined Under Namespace

Classes: MinHeap

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Heap

Returns a new instance of Heap.



17
18
19
 
# File 'lib/priorityq/heap.rb', line 17

def initialize
  @heap = [0]
end

Class Method Details

.max ⇒ Object 



9
10
11
 
# File 'lib/priorityq/heap.rb', line 9

def self.max
  new
end

.min ⇒ Object 



13
14
15
 
# File 'lib/priorityq/heap.rb', line 13

def self.min
  MinHeap.new
end

Instance Method Details

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


21
22
23
 
# File 'lib/priorityq/heap.rb', line 21

def empty?
  heap.size == 1
end

#peek ⇒ Object 



25
26
27
28
29
 
# File 'lib/priorityq/heap.rb', line 25

def peek
  return nil if empty?

  heap[1]
end

#pop ⇒ Object 



31
32
33
34
35
36
37
38
 
# File 'lib/priorityq/heap.rb', line 31

def pop
  return nil if empty?

  exchange 1, top
  value = heap.pop
  bubble_down 1
  value
end

#push(value) ⇒ Object 



40
41
42
43
 
# File 'lib/priorityq/heap.rb', line 40

def push(value)
  heap.push value
  bubble_up top
end