Class: Heap

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

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Heap

Returns a new instance of Heap.



2
3
4
 
# File 'lib/data_structures/heap.rb', line 2

def initialize
  @store = []
end

Instance Method Details

#extract ⇒ Object

Raises:

  • (ArgumentError) 


22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
# File 'lib/data_structures/heap.rb', line 22

def extract
  raise ArgumentError.new('Heap is empty') if @store.empty?
  return @store.shift if @store.length <= 2

  @store[0], @store[-1] = @store[-1], @store[0]
  head = @store.pop

  el_idx = 0
  children_indices = children_indices(el_idx)

  heapify_down(el_idx, children_indices)

  head
end

#insert(el) ⇒ Object 



11
12
13
14
15
16
17
18
19
20
 
# File 'lib/data_structures/heap.rb', line 11

def insert(el)
  @store << el

  el_idx = @store.length - 1
  parent_idx = parent_idx(el_idx)

  heapify_up(el_idx, parent_idx)

  el
end

#peek ⇒ Object

Raises:

  • (ArgumentError) 


6
7
8
9
 
# File 'lib/data_structures/heap.rb', line 6

def peek
  raise ArgumentError.new('Heap is empty') if @store.empty?
  @store.first
end