Add notes on Binary Heap

2 files changed, 80 insertions, 4 deletions

diff --git a/doc/unit/09/README.md b/doc/unit/09/README.md
index b6758da..1cca36c 100644
--- a/doc/unit/09/README.md
+++ b/doc/unit/09/README.md
@@ -22,6 +22,11 @@ Each node, `u`, has a colour which is either `red` or `black`.
 * red: is represented by the value 0.
 * black: is represented by the value 1.
 
+A red-black tree implements the SSet interface and supports
+operations `add(x)`, `remove(x)`, and `find(x)` in O(logn) worst-case time
+per operation.
+
+
 ```java
 class Node<T> extends BSTNode<Node<T>, T> {
   byte colour;
diff --git a/doc/unit/10/README.md b/doc/unit/10/README.md
index 1c6b645..9782e73 100644
--- a/doc/unit/10/README.md
+++ b/doc/unit/10/README.md
@@ -1,10 +1,39 @@
 # Heaps
 
-Eytzinger's method can represent a complete binary tree as an array.
+> a disorganized pile
 
-`2i + 1` and the right child of the node at index `i` is at
-index `right(i) = 2i +2`. The parent of the node at index `i` is at index
-`parent(i) = (i-1)/2`.
+## BinaryHeap: An implicit Binary Tree
+
+Eytzinger's method can represent a complete binary tree as an array
+by laying out the nodes of the tree in a breadth-first order.
+
+* The root is stored at position 0
+* The root's left child is stored at position 1
+* The root's right child is stored at position 2.
+
+The left child of the node at index `i` is at index `left(i) = 2i + 1`
+and the right child of the node at index `i` is at index `right(i) = 2i +2`.
+The parent of the node at index `i` is at index `parent(i) = (i-1)/2`.
+
+```plaintext
+
+           -------(0)--------
+          /                  \
+       (1)                    (2)
+      /    \               /      \
+   (3)       (4)        (5)         (6)
+  /  \      /   \       /  \       /   \
+(7)  (8)  (9)  (10)  (11)  (12)  (13)  (14)
+
+| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|
+```
+
+* left: `2i+1`
+* right: `2i+2`
+
+The binary heap implements the priority queue interface.
+Ignoring the cost of `resize()` it supports the operations
+`add(x)` and `remove(x)` in `O(logn)` time per operation.
 
 ```java
 class BinaryHeap {
@@ -20,6 +49,48 @@ class BinaryHeap {
   int parent(int i) {
     return (i-1)/2;
   }
+  boolean add(T x) {
+    if (n+1 > a.length) resize();
+    a[n++] = x;
+    bubbleUp(n-1);
+    return true;
+  }
+  void bubbleUp(int i) {
+    int p = parent(i);
+    while (i > 0 && compare(a[i], a[p]) < 0) {
+      swap(i, p);
+      i = p;
+      p = parent(i);
+    }
+  }
+  T remove() {
+    T x = a[0];
+    a[0] = a[--n];
+    trickleDown(0);
+    if (3*n < a.length) resize();
+    return x;
+  }
+  void trickleDown(int i) {
+    do {
+      int j = -1;
+      int r = right(i);
+      if (r < n && compare(a[r], a[i]) < 0) {
+        int l = left(i);
+        if (compare(a[1], a[r]) < 0) {
+          j = 1;
+        } else {
+          j = r;
+        }
+      } else {
+        int l = left(i);
+        if (l < n && compare(a[l], a[i]) < 0) {
+          j = 1;
+        }
+      }
+      if (j >= 0) swap(i, j);
+      i = j;
+    } while (i >= 0);
+  }
 }
 ```