Class: Heap

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

Overview

A Heap is a partially sorted, complete N-ary tree with the property:

  • Every node has a value larger (or smaller) than that of its children (the heap property is satisfied when a parent value equals a child value)

Implementation details:

  • Any Comparable may be used for node values.

  • Initialize a heap with a cmp_val, either 1 for a MaxHeap or -1 for a MinHeap.

  • Insertion (push) and removal (pop) are O(logb n) where n is the heap size and b is child_slots (the N in N-ary)

  • Nodes are inserted at the end of the array, and sift_up is called to reestablish the heap property.

  • Nodes are removed from the start of the array, and sift_down is called to reestablish the heap property.

  • Sift_up and sift_down are O(logb n) because they only have to check and swap nodes at each layer of the tree, and there are log(n, base b) layers to the tree.

Instance Method Summary collapse

Constructor Details

#initialize(cmp_val: 1, minheap: false, child_slots: 2) ⇒ Heap

  • defaults to a MaxHeap, with the largest node at the root

  • specify a minheap with minheap: true or cmp_val: -1



27
28
29
30
31
32
33
34
35
36
 
# File 'lib/compsci/heap.rb', line 27

def initialize(cmp_val: 1, minheap: false, child_slots: 2)
  super(child_slots: child_slots)
  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) 


115
116
117
118
119
120
121
122
123
124
125
126
 
# File 'lib/compsci/heap.rb', line 115

def heap?(idx: 0)
  check_children = []
  self.class.children_idx(idx, @child_slots).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

#heapiest(cidxs) ⇒ Object

return the heapiest idx in cidxs



103
104
105
106
107
108
109
 
# File 'lib/compsci/heap.rb', line 103

def heapiest(cidxs)
  idx = cidxs.first
  cidxs.each { |cidx|
    idx = cidx if cidx < @store.size and self.heapish?(cidx, idx)
  }
  idx
end

#heapish?(pidx, cidx) ⇒ Boolean

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

Returns:

  • (Boolean) 


97
98
99
 
# File 'lib/compsci/heap.rb', line 97

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

#peek ⇒ Object

  • return what pop would return (avoid sifting)



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

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



50
51
52
53
54
55
56
 
# File 'lib/compsci/heap.rb', line 50

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



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

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 (log base child_slots)

  • slower than sift_up because one parent vs multiple children



83
84
85
86
87
88
89
90
91
92
93
 
# File 'lib/compsci/heap.rb', line 83

def sift_down(idx)
  return self if idx >= @store.size
  cidxs = self.class.children_idx(idx, @child_slots)
  # promote the heapiest child
  cidx = self.heapiest(cidxs)
  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 (log base child_slots)



68
69
70
71
72
73
74
75
76
 
# File 'lib/compsci/heap.rb', line 68

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