263 Lecture 5

  1. RandomizeQuickSort(A):
        Shuffle(A);
        QuickSort(A);
                    
  2. Expectation of Hashing: O(n)
  3. Mergeable Heap
    Insert
    FindMin
    RemoveMin
    Make
    Merge(h_1, h_2) -> h_1 \union h_2

  4. Binomial Heaps
    Forest of Binomial Trees.
    A set of binary trees
    Each order can only appear once.
    Each binary tree is a mian heap
    At most 1 binary tree of order k.
  5. Binomial Tree
    B_k = B_{k-1} + B_{k-1}
    B_0 = A single node
    Each node has B_0 to B_{k-1} (i.e. k kids)
    |B_k| = 2^k