Binary Heaps
- Used to implement priority queues
  * Min-heap; lowest value first
  * Max-heap; highest value first
- The binary tree must be complete
  * The reheap operations depend upon this.

Heap Property
- Max-heap: The value in every node is bigger than the value in BOTH its children.

Storage in vector
- Movement up and down is fast. 
  * Reheaps are O(log(n))
  * e.g. Insertion is just a push_back instead of a Log(n) search for a leaf
- Linchpin is completeness of 'tree structure'


Sorts
- Insertion - O(n^2)
  * Effective on 'almost sorted' arrays 
- Heap - O(log(n))
  * In place, must keep track of where heap ends.
- Shell - O(n^2)
  * Effective on arrays in disarray
  * Compares distant elements, working through smaller distances.

Maps
- Entries are name(key)-value pairs. 
* C++
  > Can have multiple values for a name  (multimap)
  > Entries are referred to as pair<first,second>
  > For a regular map, inserting an entry with a particular name overwrites any previous
    + Multimaps add the value to the name (key).