Class: BinaryHeap

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

Overview

LEGACY BELOW untouched for now

Instance Method Summary collapse

Constructor Details

#initialize(cmp_val: 1, minheap: false) ⇒ BinaryHeap

defaults to a MaxHeap, with the largest node at the root specify a minheap with minheap: true or cmp_val: -1



137
138
139
140
141
142
143
144
145
146
 
# File 'lib/compsci/heap.rb', line 137

def initialize(cmp_val: 1, minheap: false)
  super()
  cmp_val = -1 if minheap
  case cmp_val
  when -1, 1
    @cmp_val = cmp_val
  else
    raise(ArgumentError, "unknown comparison value: #{cmp_val}")
  end
end

Instance Method Details

#heap?(idx: 0) ⇒ Boolean

not used internally checks that every node satisfies the heap property calls heapish? on idx’s children and then heap? on them recursively

Returns:

  • (Boolean) 


207
208
209
210
211
212
213
214
215
216
217
218
 
# File 'lib/compsci/heap.rb', line 207

def heap?(idx: 0)
  check_children = []
  self.class.children_idx(idx).each { |cidx|
    # cidx is arithmetically produced; the corresponding child may not exist
    if cidx < @store.size
      return false unless self.heapish?(idx, cidx)
      check_children << cidx
    end
  }
  check_children.each { |cidx| return false unless self.heap?(idx: cidx) }
  true
end

#heapish?(pidx, cidx) ⇒ Boolean

are values of parent and child (by index) in accordance with heap property?

Returns:

  • (Boolean) 


200
201
202
 
# File 'lib/compsci/heap.rb', line 200

def heapish?(pidx, cidx)
  (@store[pidx] <=> @store[cidx]) != (@cmp_val * -1)
end

#peek ⇒ Object

return what pop would return (avoid sifting)



167
168
169
 
# File 'lib/compsci/heap.rb', line 167

def peek
  @store.first
end

#pop ⇒ Object

remove from the front of the array move last node to root sift_down – O(log n) on heap size



158
159
160
161
162
163
164
 
# File 'lib/compsci/heap.rb', line 158

def pop
  node = @store.shift
  replacement = @store.pop
  @store.unshift replacement if replacement
  self.sift_down(0)
  node
end

#push(node) ⇒ Object

append to the array sift_up – O(log n) on heap size



150
151
152
153
 
# File 'lib/compsci/heap.rb', line 150

def push(node)
  @store << node
  self.sift_up(@store.size - 1)
end

#sift_down(idx) ⇒ Object

called recursively idx represents the node suspected to violate the heap intended to be O(log n) on heap size



187
188
189
190
191
192
193
194
195
196
197
 
# File 'lib/compsci/heap.rb', line 187

def sift_down(idx)
  return self if idx >= @store.size
  lidx, ridx = self.class.children_idx(idx)
  # promote the heapiest child
  cidx = self.heapish?(lidx, ridx) ? lidx : ridx
  if !self.heapish?(idx, cidx)
    @store[idx], @store[cidx] = @store[cidx], @store[idx]   # swap
    self.sift_down(cidx)
  end
  self
end

#sift_up(idx) ⇒ Object

called recursively idx represents the node suspected to violate the heap intended to be O(log n) on heap size



174
175
176
177
178
179
180
181
182
 
# File 'lib/compsci/heap.rb', line 174

def sift_up(idx)
  return self if idx <= 0
  pidx = self.class.parent_idx(idx)
  if !self.heapish?(pidx, idx)
    @store[idx], @store[pidx] = @store[pidx], @store[idx]   # swap
    self.sift_up(pidx)
  end
  self
end