Class: BinaryMinHeap

Inherits:
Object
  • Object
show all
Defined in:
lib/utils/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
6
 
# File 'lib/utils/heap.rb', line 2

def initialize(&prc)
  @store = []
  @index_map = {}
  @prc = prc || Proc.new { |a, b| a <=> b }
end

Class Method Details

.child_indices(len, parent_index) ⇒ Object 



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

def self.child_indices(len, parent_index)
  [2 * parent_index + 1, 2 * parent_index + 2].select { |idx| idx < len }
end

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



64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
 
# File 'lib/utils/heap.rb', line 64

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

  while parent_idx <= parent_index(len - 1)
    children = child_indices(len, parent_idx)

    if children.length == 1
      smallest_child_idx = children[0]
    else
      child1_idx, child2_idx = children[0], children[1]

      if prc.call(array[child1_idx], array[child2_idx]) <= 0
        smallest_child_idx = child1_idx
      else
        smallest_child_idx = child2_idx
      end
    end

    if prc.call(array[parent_idx], array[smallest_child_idx]) > 0
      swap!(array, index_map, parent_idx, smallest_child_idx)
      parent_idx = smallest_child_idx
    else
      break
    end

  end

  array
end

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



94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
 
# File 'lib/utils/heap.rb', line 94

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

  while child_idx > 0
    parent_idx = parent_index(child_idx)

    if prc.call(array[parent_idx], array[child_idx]) > 0
      swap!(array, index_map, parent_idx, child_idx)
      child_idx = parent_idx
    else
      break
    end

  end

  array
end

.parent_index(child_index) ⇒ Object 



56
57
58
59
60
61
62
 
# File 'lib/utils/heap.rb', line 56

def self.parent_index(child_index)
  if child_index == 0
    return nil
  else
    (child_index - 1) / 2
  end
end

.swap!(array, index_map, i1, i2) ⇒ Object 



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

def self.swap!(array, index_map, i1, i2)
  array[i1], array[i2] = array[i2], array[i1]
  index_map[parent_val], index_map[child_val] = child_idx, parent_idx
end

Instance Method Details

#count ⇒ Object 



8
9
10
 
# File 'lib/utils/heap.rb', line 8

def count
  @store.length
end

#peek ⇒ Object 



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

def peek
  return nil if count == 0
  @store.first
end

#pop ⇒ Object 



12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
# File 'lib/utils/heap.rb', line 12

def pop
  return nil if count == 0

  self.class.swap!(@store, @index_map, 0, count - 1)

  val = @store.pop
  @index_map.delete(val)

  unless count == 0
    self.class.heapify_down(@store, @index_map, 0, &prc)
  end

  val
end

#push(val) ⇒ Object 



32
33
34
35
36
 
# File 'lib/utils/heap.rb', line 32

def push(val)
  @store << val
  @index_map[val] = count - 1
  self.class.heapify_up(@store, @index_map, count - 1, &prc)
end

#reduce!(val) ⇒ Object 



38
39
40
41
 
# File 'lib/utils/heap.rb', line 38

def reduce!(val)
  index = @index_map[val]
  self.class.heapify_up(@store, @index_map, index, &prc)
end