Class: CompSci::Heap
- Inherits:
-
CompleteTree
- Object
- CompleteTree
- CompSci::Heap
- 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
Instance Method Summary collapse
-
#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.
-
-
#heapiest(cidxs) ⇒ Object
return the heapiest idx in cidxs.
-
#heapish?(pidx, cidx) ⇒ Boolean
are values of parent and child (by index) in accordance with heap property?.
-
#initialize(cmp_val: 1, minheap: false, child_slots: 2) ⇒ Heap
constructor
-
defaults to a MaxHeap, with the largest node at the root * specify a minheap with minheap: true or cmp_val: -1.
-
-
#peek ⇒ Object
-
return what pop would return (avoid sifting).
-
-
#pop ⇒ Object
-
remove from the front of the array * move last node to root * sift_down – O(log n) on heap size.
-
-
#push(node) ⇒ Object
-
append to the array * sift_up – O(log n) on heap size.
-
-
#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.
-
-
#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).
-
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
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?
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 |