## Lecture 24 - 03/15

### Heaps and Priority Queues

• Use a priority queue (such as minimum/maximum priority queue) to get the M$M$ "smallest"/"largest"/"best"/... elements in dataset so far
• Priority queue interface:

/** (Min) Priority Queue: Allowing tracking and removal of the
* smallest item in a priority queue. */
public interface MinPQ<Item> {
/** Adds the item to the priority queue. */

/** 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();
}

• Naive implementation: store all the N$N$ elements, sort them, and then find smallest/biggest/...
• Takes Θ(N)$\Theta(N)$ memory which is huge
• Goal is to take Θ(M)$\Theta(M)$ memory instead, where M$M$ is
• Better implementation: Track M$M$ largest items:
• One by one, add all elements to a MinPQ
• Whenever size of the PQ >M$> M$, remove the smallest element from the PQ
• At end, we are left with M$M$ largest items of some set of data
• Have done this with only M$M$ memory

#### Implementing a PQ using a Heap:

• Note: not related to "the Heap" of a computer/computer memory
• We will use a binary min-heap
• This is a binary tree that is:
• Complete (missing items are only at the bottom if any, and all nodes are as far left as possible)
• Obeys min-heap property (all nodes are smaller than or equal to both their children)
• Only need to meet this min-heap property; ordering of nodes otherwise doesn't matter
• The smallest element in a MinPQ will thus be the root node!
• To insert a node into a heap:
• Insert at end of heap (left-most position open at lowest level of tree)
• Swim the node up to the appropriate place:
• Compare current node with parent node (if parent exists)
• If parent is greater than current node, exit swim function (swimming not needed)
• Else, swap parent and current node positions, and then call swim function again on the current node (which now has a new position one level higher)
• Idea: recursively call swim on the new node until it is at the right position in the tree (the tree satisfies the min-heap property)
• To see the smallest element in the heap, return value of root of tree
• To remove smallest element from the heap:
• Delete root from tree (may need to store this in some temp variable to return later)
• Take the last element in the heap (right-most node at lowest level of tree), and place it at the root
• Sink the node down to the appropriate place:
• If the current node is smaller than all its children (anywhere from 1$1$ to 2$2$) or has no children, exit since the node is in the proper position and sinking is no longer needed
• Otherwise, swap the current node with its smallest child, and call the sink function again on the current node (which now has a new position one level lower)
• Idea: recursively call sink on the node until it is at the right position in the tree (the tree satisfies the min-heap property)
• Performance of heap: logN$\log N$ time amortized
• Note: may need to have constructor that takes in a comparator object or make the class have a generic type that extends Comparable (in other words, may need to specify how elments in the heap are compared to each other)

#### Representing Trees in Java

1. Create a mapping from parent nodes to children nodes (similar to having a linked-list of nodes and pointers)
1. Fixed-width nodes (like in BSTs)
2. Variable-width nodes (each parent node has an array of children nodes)
3. Sibling tree (each parent node has a pointer to a "first-born" child, whom in turn points to his next-oldest sibling, who in turn points to the next-oldest sibling, ... (essentially a linked-list of children nodes))
2. Store keys in an array, and store parents in another array (indices between the two arrays correspond to the same node; order of nodes in the arrays has some correspondance to order of nodes in the actual tree)
3. Cleaner approach, very nice for heaps: store keys in array; assume the tree is complete
• The parent of a node at index k$k$ is at index k / 2$k~/~2$
• The left child of a node at index k$k$ is at index 2k$2k$
• The right child of a node at index k$k$ is at index 2k+1$2k + 1$
• Note: can use array's size method to find index of last element in array/heap

#### Summary

• We looked at Lists (Stack/Queue/Deque), Maps (HashMap/TreeMap), Sets, PQs, and Disjoint Sets
• We looked at implementing them with BSTs, 2-3 Trees, LLRBs, Hash Tables, Linked Lists, Resizing Arrays, Heaps, and WeightedQuickUnion
• We looked at the various performance costs associated with each implementation
• This includes amortized runtime, such as with Hash Tables