Class: CompSci::Heap

Inherits:
CompleteTree 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 Attribute Summary

Attributes inherited from CompleteTree

#array

Instance Method Summary collapse

Methods inherited from CompleteTree

#bf_search, children_idx, #df_search, #display, gen, #last_idx, parent_idx, #size

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



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

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) 


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

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 < @array.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



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

def heapiest(cidxs)
  idx = cidxs.first
  cidxs.each { |cidx|
    idx = cidx if cidx < @array.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) 


95
96
97
 
# File 'lib/compsci/heap.rb', line 95

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

#peek ⇒ Object

  • return what pop would return (avoid sifting)



58
59
60
 
# File 'lib/compsci/heap.rb', line 58

def peek
  @array.first
end

#pop ⇒ Object

  • remove from the front of the array

  • move last node to root

  • sift_down – O(log n) on heap size



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

def pop
  node = @array.shift
  replacement = @array.pop
  @array.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



39
40
41
42
 
# File 'lib/compsci/heap.rb', line 39

def push(node)
  @array.push(node)
  self.sift_up(@array.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



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

def sift_down(idx)
  return self if idx >= @array.size
  cidxs = self.class.children_idx(idx, @child_slots)
  # promote the heapiest child
  cidx = self.heapiest(cidxs)
  if !self.heapish?(idx, cidx)
    @array[idx], @array[cidx] = @array[cidx], @array[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)



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

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