Introduction to Probability

Multivariable Calculus

Algorithms: Part II

Algorithms: Part I

Introduction to Software Design and Architecture

Calculus Two: Sequences and Series

LAFF Linear Algebra

Stanford Machine Learning

Calculus One

Computational Thinking

Effective Thinking Through Mathematics

CS50 Introduction to Computer Science


Week 4 - Priority Queues & Elementary Symbols

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.

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;
  • 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);
      pq[N+1] = null;
      return max;


  • 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


Elementary Symbols

  • Key-value pair abstraction.

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

  • Ordered APIs

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.