Class: BinaryMinHeap

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

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(&prc) ⇒ BinaryMinHeap

Returns a new instance of BinaryMinHeap.



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

def initialize(&prc)
  @prc = prc
  @store = Array.new
end

Class Method Details

.child_indices(len, parent_idx) ⇒ Object 



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

def self.child_indices(len, parent_idx)
  first_child_idx = ( parent_idx * 2 ) + 1
  second_child_idx = ( parent_idx * 2 ) + 2

  [first_child_idx, second_child_idx].select do |idx|
    idx < len && idx > -1
  end
end

.heapify_down(array, parent_idx, len = array.length, &prc) ⇒ Object 



46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
# File 'lib/simms_structures/heap.rb', line 46

def self.heapify_down(array, parent_idx, len = array.length, &prc)
  prc ||= Proc.new { |a, b| a <=> b }

  child_idxs = BinaryMinHeap.child_indices(len, parent_idx)
  if child_idxs.empty?
    return array
  elsif child_idxs.count == 1
    target_child = child_idxs.first
  else
    if prc.call(array[child_idxs.first], array[child_idxs.last]) > -1
      target_child = child_idxs.last
    else
      target_child = child_idxs.first
    end
  end

  if prc.call(array[parent_idx], array[target_child]) > -1
    array[parent_idx], array[target_child] = array[target_child], array[parent_idx]
    BinaryMinHeap.heapify_down(array, target_child, len, &prc)
  end
  array
end

.heapify_up(array, child_idx, len = array.length, &prc) ⇒ Object 



69
70
71
72
73
74
75
76
77
78
79
 
# File 'lib/simms_structures/heap.rb', line 69

def self.heapify_up(array, child_idx, len = array.length, &prc)
  return if child_idx == 0
  prc ||= Proc.new { |a, b| a <=> b }

  parent_idx = BinaryMinHeap.parent_index(child_idx)
  if prc.call(array[parent_idx], array[child_idx]) > -1
    array[parent_idx], array[child_idx] = array[child_idx], array[parent_idx]
    BinaryMinHeap.heapify_up(array, parent_idx, len, &prc)
  end
  array
end

.parent_index(child_idx) ⇒ Object 



41
42
43
44
 
# File 'lib/simms_structures/heap.rb', line 41

def self.parent_index(child_idx)
  raise 'root has no parent' if child_idx == 0
  ( child_idx - 1 ) / 2
end

Instance Method Details

#count ⇒ Object 



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

def count
  @store.length
end

#extract ⇒ Object 



15
16
17
18
19
20
21
 
# File 'lib/simms_structures/heap.rb', line 15

def extract
  last = @store.length - 1
  @store[0], @store[last] = @store[last], @store[0]
  output = @store.pop
  BinaryMinHeap.heapify_down(@store, 0)
  output
end

#insert(val) ⇒ Object 



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

def insert(val)
  @store.push(val)
  BinaryMinHeap.heapify_up(@store, @store.length - 1)
end

#peek ⇒ Object 



11
12
13
 
# File 'lib/simms_structures/heap.rb', line 11

def peek
  @store.last
end