lib/compsci/heap.rb in compsci-0.0.1.1 vs lib/compsci/heap.rb in compsci-0.0.2.1

@@ -34,17 +34,20 @@
     else
       raise(ArgumentError, "unknown comparison value: #{cmp_val}")
     end
   end
 
-  # append to the array; sift_up
+  # append to the array
+  # sift_up -- O(log n) on heap size
   def push(node)
     @store << node
     self.sift_up(@store.size - 1)
   end
 
-  # remove from the front of the array; move last node to root; sift_down
+  # remove from the front of the array
+  # move last node to root
+  # sift_down -- O(log n) on heap size
   def pop
     node = @store.shift
     replacement = @store.pop
     @store.unshift replacement if replacement
     self.sift_down(0)
@@ -54,42 +57,49 @@
   # return what pop would return (avoid sifting)
   def peek
     @store.first
   end
 
-  # called recursively; idx represents the node suspected to violate the heap
+  # called recursively
+  # idx represents the node suspected to violate the heap
+  # intended to be O(log n) on heap size
   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
+      @store[idx], @store[pidx] = @store[pidx], @store[idx]   # swap
       self.sift_up(pidx)
     end
     self
   end
 
-  # called recursively; idx represents the node suspected to violate the heap
+  # called recursively
+  # idx represents the node suspected to violate the heap
+  # intended to be O(log n) on heap size
   def sift_down(idx)
     return self if idx >= @store.size
     lidx, ridx = self.class.children_idx(idx)
-    # take the child most likely to be a good parent
+    # 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
+      @store[idx], @store[cidx] = @store[cidx], @store[idx]   # swap
       self.sift_down(cidx)
     end
     self
   end
 
   # are values of parent and child (by index) in accordance with heap property?
   def heapish?(pidx, cidx)
     (@store[pidx] <=> @store[cidx]) != (@cmp_val * -1)
   end
 
-  # not used internally; checks that every node satisfies the heap property
+  # not used internally
+  # checks that every node satisfies the heap property
+  # calls heapish? on idx's children and then heap? on them recursively
   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
     }