Week 4 - Priority Queues & Elementary Symbols

1. Priority Queues

  • Insert and delete items. Which item to delete?
    • Stack. Remove the item most recently added.
    • Queue. Remove the item least recently added.
    • Randomized queue. Remove a random item.
    • Priority queue. Remove the largest (or smallest) item.

1.1. Binary Tree

  • Empty or node with links to left and right binary trees.

Complete binary tree

  • Perfectly balanced, except for bottom level.
  • Height of complete tree with N nodes is lg N⎦.

Binary heap representations

  • Array representation of a heap-ordered complete binary tree.
  • Heap-ordered binary tree.
    • Keys in nodes.
    • Parent's key no smaller than children's keys.
  • Largest key is a[1], which is root of binary tree.
  • Can use array indices to move through tree.
  • Parent of node at k is at k/2.
  • Children of node at k are at 2k and 2k+1.
  • Insertion in a heap

    • Add node at end, then swim it up.

        private void swim(int k) {
            while (k > 1 && less(k/2, k)) {
                exch(k, k/2);
                k = k/2; 
            } 
        }
        public void insert(Key x) {
            pq[++N] = x;
            swim(N);
        }
      
  • Delete the maximum in a heap

    • Exchange root with node at end, then sink it down.

        private void sink(int k) {
            while(2*k <= N) {
                int j = 2*k;
                if(j < N && less(j, j+1)) j++;
                if(!less(k, j)) break;
                exch(k, j);
                k = j;
            }
        }
        public Key delMax() {
            Key max = pq[1];
            exch(1, N-1);
            sink(1);
            pq[N+1] = null;
            return max;
        }
      

1.2. Heapsort

  • Step 1: Build heap using bottom-up method.

      for (int k = N/2; k >= 1; k--) 
          sink(a, k, N);
    
    • N is just used to count

  • Step 2: Remove the maximum, one at a time. exchange the first element(maximum one) to the end, then sink the first element.

      while (N > 1) {
          exch(a, 1, N--);
          sink(a, 1, N);
      }
    
    • N is just used to count

1.3. Summary

2. Elementary Symbols

  • Key-value pair abstraction.

    • Insert a value with specified key.
    • Given a key, search for the corresponding value.
  • APIs

  • Ordered APIs

2.1. Binary Search Trees

  • A BST is a binary tree in symmetric order.
    • A binary tree is either:
      • Empty.
      • Two disjoint binary trees (left and right).
    • Symmetric order. Each node has a key, and every node’s key is:
      • Larger than all keys in its left subtree.
      • Smaller than all keys in its right subtree
  • A Node is comprised of four fields:

    • A Key and a Value.
    • A reference to the left and right subtree.
  • Search. If less, go left; if greater, go right; if equal, search hit.

  • Insert. If less, go left; if greater, go right; if null, insert.
  • Get. Return value corresponding to given key, or null if no such key.
  • Put. Associate value with key.

    • Search for key, then two cases:
      • Key in tree ⇒ reset value.
      • Key not in tree ⇒ add new node.
  • Different tree shapes

  • If N distinct keys are inserted into a BST in random order, the expected number of compares for a search/insert is ~ 2 ln N.

Ordered operations

  • Minimum. Smallest key in table.
  • Maximum. Largest key in table.
  • Floor. Largest key ≤ a given key.
  • Ceiling. Smallest key ≥ a given key.
    • Thinking this partially.
    • For example:
        1. initial the result is null.
        1. just check S, E and X.
        1. G < S, so still null. All of the right of S should be bigger that S, so we continue check the left side E, A and R.
        1. E < G, so E is a candidate. All of the left side of E should be less that E, So we continue check the right side of E: R, H and null.
        1. R > G, So the left side of R: H
        1. H > G, and H is the leaf. So E is the answer.
  • Counts
    • In each node, we store the number of nodes in the subtree rooted at that node; to implement size(), return the count at the root.
  • Rank

    • how many keys < k?
  • Inorder traversal (Iteration)

    • Traverse left subtree.
    • Enqueue key.
    • Traverse right subtree.

BST: ordered symbol table operations summary

Hibbard Deletion

  • To delete a node with key k: search for node t containing key k.
  • Case 0. [0 children] Delete t by setting parent link to null.

  • Case 1. [1 child] Delete t by replacing parent link.

  • Case 2. [2 children]

    • Find successor x of t.
    • Delete the minimum in 's right subtree.
    • Put x in t's spot.
  • analysis

    • Unsatisfactory solution. After some deleting, the tree is becoming less balanced.

results matching ""

    No results matching ""