Commit 67a2c78

@@ -126,4 +126,3 @@ The following properties are satisfied before and after any operation:
 * no-red-edge: No two red nodes are adjacent. (except the root, `u.colour + u.parent.colour >= 1`)
 
 The root is black.
-

@@ -0,0 +1,31 @@
+# Heaps
+
+Eytzinger's method can represent a complete binary tree as an array.
+
+`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`.
+
+```java
+class BinaryHeap {
+  T[] a;
+  int n;
+
+  int left(int i) {
+    return 2*i + 1;
+  }
+  int right(int i) {
+    return 2*i + 2;
+  }
+  int parent(int i) {
+    return (i-1)/2;
+  }
+}
+```
+
+A `BinaryHeap` uses this technique to implicitly represent a complete
+binary tree in which the elements are `heap-ordered.`
+
+heap-ordered: The value stored at any index `i` is not smaller than the value stored at index `parent(i)`, with the exception of the root value, `i = 0`.
+The smallest value in the priority Queue is at position 0.
+

@@ -0,0 +1,66 @@
+# Comparison-Based Sorting
+
+* merge sort O(nlogn)
+* quick sort O(nlogn)
+* heap sort O(nlogn)
+
+`compare(a,b)`
+
+* -1: a < b
+* 0: a == b
+* +1: a > b
+
+## Merge-Sort
+
+is a classic recursive divide and conquer.
+
+* if `a` is at most 1 then `a` is sorted.
+* else we split `a` into two halves
+  * `a0 = a[0...(n/2)-1]`
+  * `a1 = a[(n/2)...n-1]`
+  * merge a0, a1
+
+```java
+void mergeSort(T[] a, Comparator<T> c) {
+  if (a.length <= 1) return;
+
+  T[] a0 = Arrays.copyOfRange(a, 0, a.length/2);
+  T[] a1 = Arrays.copyOfRange(a, a.length/2, a.length);
+  mergeSort(a0, c);
+  mergeSort(a1, c);
+  merge(a0, a1, a, c);
+}
+```
+
+## Quicksort
+
+Unlike mergesort which does merging after solving the two subproblems,
+quicksort does all of its work upfront.
+
+1. pick a random `pivot` element `x` from `a`
+2. partition `a` into the set of elements less than `x`, the set of elements equal to `x` and the set of elements greater than `x`.
+3. recursively sort the first and third sets in this partition.
+
+```java
+void quickSort(T[] a, Comparator<T> c) {
+  quickSort(a, 0, a.length, c);
+}
+void quickSort(T[] a, int i, int n, Comparator<T> c) {
+  if (n <= 1) return;
+  T x = a[i + rand.nextInt(n)];
+  int p = i - 1, j = i, q = i+n;
+
+  while (j < q) {
+    int comp = compare(a[j], x);
+    if (comp < 0) {
+      swap(a, j++,  ++p);
+    } else if (comp > 0) {
+      swap(a, j, --q);
+    } else {
+      j++;
+    }
+  }
+  quickSort(a, i, p-i+1, c);
+  quickSort(a, q, n-(q-i), c);
+}
+```