Class: DataStructures101::Heap

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

Overview

Heap implementation

Author:

  • Rene Hernandez

Since:

  • 0.3

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(*args, min_heap: false) ⇒ Heap

Returns a new instance of Heap.

Since:

  • 0.3



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

def initialize(*args, min_heap: false)
  @data = args
  @min_heap = min_heap
  @heap_check = ->(i, j) { return @data[i] >= @data[j] }

  if @min_heap
    @heap_check = ->(i, j) { return @data[i] <= @data[j] }
  end

  build_heap
end

Instance Attribute Details

#min_heap ⇒ Object (readonly)

Since:

  • 0.3



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

def min_heap
  @min_heap
end

Instance Method Details

#[](i) ⇒ Object

Since:

  • 0.3



27
28
29
 
# File 'lib/data_structures_101/heap.rb', line 27

def [](i)
  @data[i]
end

#left(i) ⇒ Object

Since:

  • 0.3



52
53
54
 
# File 'lib/data_structures_101/heap.rb', line 52

def left(i)
  2 * i + 1
end

#merge(heap) ⇒ Object

Since:

  • 0.3



46
47
48
49
50
 
# File 'lib/data_structures_101/heap.rb', line 46

def merge(heap)
  new_array = @data + heap.instance_variable_get(:@data)

  Heap.new(new_array, min_heap: self.min_heap)
end

#parent(i) ⇒ Object

Since:

  • 0.3



60
61
62
 
# File 'lib/data_structures_101/heap.rb', line 60

def parent(i)
  (i - 1) / 2
end

#pop ⇒ Object

Since:

  • 0.3



39
40
41
42
43
44
 
# File 'lib/data_structures_101/heap.rb', line 39

def pop
  result = @data.first
  @data[0] = @data.pop
  heapify(0)
  result
end

#push(*values) ⇒ Object

Since:

  • 0.3



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

def push(*values)
  values.each do |val|
    @data.push(val)
    upheap(@data.size - 1)
  end
  self
end

#right(i) ⇒ Object

Since:

  • 0.3



56
57
58
 
# File 'lib/data_structures_101/heap.rb', line 56

def right(i)
  2 * (i + 1)
end

#size ⇒ Object

Since:

  • 0.3



23
24
25
 
# File 'lib/data_structures_101/heap.rb', line 23

def size
  @data.size
end