Heaps and Priority Queues

Priority Queue

A data structure that is for quickly finding the smallest or largest element instead of quickly searching

/** (Min) Priority Queue: Allowing tracking and removal of 
  * the smallest item in a priority queue. */
public interface MinPQ<Item extends Comparable<Item>> {
    /** Adds the item to the priority queue. */
    public void add(Item x);
    /** Returns the smallest item in the priority queue. */
    public Item getSmallest();
    /** Removes the smallest item from the priority queue. */
    public Item removeSmallest();
    /** Returns the size of the priority queue. */
    public int size();
}

• Can only interact with the smallest / larges items

Implementation

• Ordered Array

  • add: Θ(N)
  • getSmallest: Θ(1)
  • removeSmallest: Θ(1)

• Bushy BST

  • add: Θ(logN)
  • getSmallest: Θ(logN)
  • removeSmallest: Θ(logN)

• HashTable

  • add: Θ(1)
  • getSmallest: Θ(N)
  • removeSmallest: Θ(N)

Better implementation: Heap

Heaps

Defining a binary min-heap as being complete and obeying min-heap property:

• Min-heap: Every node is less than or equal to both of its children
• Complete: Missing items only at the bottom level (if any), all nodes are as far left as possible.

Heap Operations

• add: Add to the end of heap temporarily. Swim up the hierarchy to the proper place.
  • Swimming involves swapping nodes if child < parent
  • Θ(logN)
• getSmallest: Return the root of the heap
  • This is guaranteed to be the minimum by our min-heap property
  • Θ(1)
• removeSmallest: Swap the last item in the heap into the root. Sink down the hierarchy to the proper place.
  • Sinking involves swapping nodes if parent > child. Swap with the smallest child to preserve min-heap property.

Tree Representation

Node Mapping Trees

In these approaches, we store explicit references of children

1. Fixed width nodes

   public class Tree1A<Key> {
     Key k;
     Tree1A left;
     Tree1A middle;
     Tree1A right;
     ...
   }

   

2. Variable-width nodes

     public class Tree1B<Key> {
     Key k;
     Tree1B[] children;
     ...

   

   • awkward traversal
   • worse performance

3. Sibling Tree

     public class Tree1C<Key> {
       Key k;
       Tree1C favoredChild;
       Tree1C sibling;
       ...
     }

   

Array Based Trees

Much like the Disjoint Sets, we use arrays to store keys and parents

• Key[] keys stores key value, whose index is used in parents to lookup its parent's index
• int[] parents stores the index of the parent of a key in keys
• To look up the parent, parent == keys[parents[keys.indexOf(key)]]

public class Tree2<Key> {
  Key[] keys;
  int[] parents;
  ...
}

• The level-order of the tree matches the order of keys exactly
• parents is redundent
• The tree is complete

So this can be simplified into

public class TreeC<Key> {
  Key[] keys;
  ...
}

Swimming in an Array Based Tree

public void swim(int k) {
    if (keys[parent(k)] > keys[k]) {
       swap(k, parent(k));
       swim(parent(k));              
    }
}

parent(k) returns the (index of) parent of the given (index of) k

/**
 * Given the structure of an array based tree,
 * the parent() is simple
 * @param k - The index of a key
 * @return The index of the parent of k
 */
private int parent(int k) {
  return (k + 1) / 2 - 1
}

private int leftChild(int k) {
  return k * 2 + 1;
}

private int rightChild(int k) {
  return (k + 1) * 2;
}

PQ Implementation

Using Heap to implement PQ:

• add Θ(logN)
• getSmallest Θ(1)
• removeSmallest Θ(logN)

Notes:

• Runtime is averaged, since the array have to resize
• BST's can have constant time getSmallest if pointer is stored to smallest element
• Array-based heaps take around 1/3rd the memory it takes to represent a heap using approach 1A (direct pointers to children)

My Implementation:

public class ArrayMinHeap<K extends Comparable<K>> implements MinHeap<K> {
    private K[] keys;
    private int size;
    private final int INITIAL_SIZE = 10;
    private final int RESIZE_MULTIPLIER = 2;
    private final double RESIZE_RATIO = 0.75;

    public ArrayMinHeap() {
        keys = (K[]) new Comparable[INITIAL_SIZE];
        size = 0;
    }

    /**
     * @return The smallest (first) element in the heap
     * @throws ArrayIndexOutOfBoundsException When there is nothing in the heap
     */
    public K getMin() throws ArrayIndexOutOfBoundsException {
        if (size == 0) {
            throw new ArrayIndexOutOfBoundsException(
                    "ArrayMinHeap: Expected more than 1 element, got 0.");
        }
        return keys[0];
    }

    /**
     * @return The size of the heap
     */
    public int size() {
        return size;
    }

    /**
     * Add an element into the heap
     * @param key The key to add
     * @return The heap itself
     */
    public MinHeap<K> add(K key) {
        if ((double) size / keys.length > RESIZE_RATIO) {
            enlarge();
        }
        keys[size] = key;
        swim(size);
        size++;
        return this;
    }

    /**
     * From bottom to top, insert the last element of the
     * heap up to the right position.
     * @param index The current index (position) of swimming
     */
    private void swim(int index) {
        int parent = parent(index);
        if (keys[parent].compareTo(keys[index]) > 0) {
            swap(index, parent);
            swim(parent);
        }
    }

    /**
     * From top to bottom, insert the top element of the
     * heap down to the right position.
     * @param current The current index (position) of diving
     */
    private void dive(int current) {
        K currentKey = keys[current];
        int parent = parent(current);
        K parentKey = keys[parent];
        if (current != 0) {
            if (currentKey.compareTo(parentKey) < 0) {
                swap(current, parent);
            } else {
                // Already in position, returning
                return;
            }
        }
        int left = leftChild(current);
        int right = rightChild(current);
        if (current == size || left >= size) {
            return;
        }
        if (right >= size) {
            dive(left);
            return;
        }
        K leftKey = keys[left];
        K rightKey = keys[right];
        // Dive the smaller child
        if (leftKey.compareTo(rightKey) < 0) {
           dive(left);
        } else {
           dive(right);
        }
    }

    /**
     * Swap two keys given each one's index
     * @param a Index of one key
     * @param b Index of another key
     */
    private void swap(int a, int b) {
        K tmpKey = keys[a];
        keys[a] = keys[b];
        keys[b] = tmpKey;
    }

    /**
     * Delete the minimum item in the heap
     * @return The deleted minimum item
     * @throws ArrayIndexOutOfBoundsException When there is no more to delete
     */
    public K deleteMin() throws ArrayIndexOutOfBoundsException {
        if (size == 0) {
            throw new ArrayIndexOutOfBoundsException(
                    "ArrayMinHeap: Expected more than 1 element, got 0.");
        }
        K min = keys[0];
        keys[0] = keys[size - 1];
        keys[size - 1] = null;
        size--;
        if (size > INITIAL_SIZE && (double) size / keys.length < 1 - RESIZE_RATIO) {
            shrink();
        }
        dive(0);
        return min;
    }

    /**
     * Resize the [keys] and [values] bigger
     * The resize ratio should be checked by the caller
     */
    private void enlarge() {
        K[] newKeys = (K[]) new Comparable[keys.length * RESIZE_MULTIPLIER];
        System.arraycopy(keys, 0, newKeys, 0, size);
        keys = newKeys;
    }

    /**
     * Resize the [keys] and [values] smaller
     * The resize ratio and minimal length should be checked by the caller
     */
    private void shrink() {
        K[] newKeys = (K[]) new Comparable[keys.length / RESIZE_MULTIPLIER];
        System.arraycopy(keys, 0, newKeys, 0, size);
        keys = newKeys;
    }

    /**
     * Get the parent's index of a given index of an element
     * @param index Index of the element to lookup
     * @return The index of it's parent, if index is root, return itself
     */
    private static int parent(int index) {
        if (index == 0) {
            return 0;
        }
        return (index + 1) / 2 - 1;
    }

    /**
     * Get the left child's index of a given index of an element
     * Whether the return value is out of bound should be checked by caller
     * @param index Index of the element to lookup
     * @return The index of left child
     */
    private static int leftChild(int index) {
        return index * 2 + 1;
    }

    /**
     * Get the right child's index of a given index of an element
     * Whether the return value is out of bound should be checked by caller
     * @param index Index of the element to lookup
     * @return The index of right child
     */
    private static int rightChild(int index) {
        return (index + 1) * 2;
    }
}

Extra: Implementing the Stack Using a PQ