- Use a priority queue (such as minimum/maximum priority queue) to get the
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. */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();}- Naive implementation: store all the
N elements, sort them, and then find smallest/biggest/...- Takes
Θ(N) memory which is huge - Goal is to take
Θ(M) memory instead, whereM is

- Takes
- Better implementation: Track
M largest items:- One by one, add all elements to a
`MinPQ`

- Whenever size of the PQ
>M , remove the smallest element from the PQ - At end, we are left with
M largest items of some set of data - Have done this with only
M memory

- One by one, add all elements to a

- 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 to2 ) 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)

- If the current node is smaller than all its children (anywhere from

- Performance of heap:
logN 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)

- Create a mapping from parent nodes to children nodes (similar to having a linked-list of nodes and pointers)
- Fixed-width nodes (like in BSTs)
- Variable-width nodes (each parent node has an array of children nodes)
- 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))

- 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)
- Cleaner approach, very nice for heaps: store keys in array; assume the tree is complete
- The parent of a node at index
k is at indexk / 2 - The left child of a node at index
k is at index2k - The right child of a node at index
k is at index2k+1 - Note: can use array's size method to find index of last element in array/heap

- The parent of a node at index

- 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