Priority Queues & Heaps

Review: Trees

• Binary Search Trees (BSTs):

  • Implement an ordered mapping ADT if keys are comparable.

  • Operations include: get, put, floor, ceil, remove, contains.

  • Running times are proportional to the height of the tree.

  • Worst-case scenario (unbalanced BST): degrades to a linear structure with O(n) time complexity.

  • Self-balancing BSTs: height is always O(log n), resulting in O(log n) time complexity for operations.

Topics

• Priority Queues

• Heaps & Implementation

• Building a Heap from a List

• Changing Item Priorities

• Heapsort

The Priority Queue

• Stores a collection of items, each with a priority.

• Key operations:

  • insert(item, priority): Adds an item with a given priority to the collection.

  • peekmin(): Returns the item with the highest priority (ties are broken arbitrarily).

  • removemin(): Removes and returns the item with the highest priority (ties are broken arbitrarily).

• Applications: operating systems, job scheduling, and network routers.

Priority Queue Implementation: ListPQ

• A basic implementation using a list in Python.

• Class ListPQ:

  • __init__(self): Initializes an empty list self._L.

  • insert(self, n): Appends the element n to the list.

  • peekMin(self): Returns the minimum element in the list using the min() function.

  • removeMin(self):

    • Finds the minimum element (minNum) in the list.

    • Removes minNum from the list.

    • Returns minNum.

The Priority Queue: Running Times

• Analyzing the time complexity of ListPQ operations:

  • insert(): $O(1)$, as it simply appends to the list.

  • peekMin(): $O(n)$, as it requires traversing the list to find the minimum element.

  • removeMin(): $O(n)$, due to the min() and remove() operations, both of which may require traversing the list.

• Question: What if we maintained a sorted list?

The Priority Queue: SortedListPQ

• An alternative implementation that keeps the list sorted.

• Class SortedListPQ:

  • __init__(self): Initializes an empty list self._L.

  • insert(self, n):

    • Appends the element n to the list.

    • Sorts the list in reverse order using self._L.sort(reverse=True). Descending sort places min at the end of list.

  • peekmin(self): Returns the last element of the list (self._L[-1]), which is the minimum element.

  • removemin(self):

    • Assigns the last element of the list (self._L[-1]) to minNum.

    • Removes the last element using self._L.pop().

    • Returns minNum.

SortedListPQ: Running Times

• insert(): $O(n)$, because of the sorting operation self._L.sort()

• peekMin(): $O(1)$, as it directly accesses the last element.

• removeMin(): $O(1)$, as it simply pops the last element.

Transition to Heaps

• Inefficiency reminder: The SortedListPQ still has the inefficiency of $O(n)$ for insert.

• Question: can we do better?

• Solution: Heaps

Heaps

• A (min) heap is a binary tree with two key properties:

  • Heap-ordered: Each node is smaller than its children, ensuring the smallest node is always the root.

  • Complete: The tree has minimal height, with leaf nodes in the leftmost positions.

• Implications:

  • Every path from the root to a leaf is sorted in ascending order.

  • There is no specific relationship mandated between sibling nodes.

Heaps: Operations

• Featured operations:

  • insert(item, priority): Adds an item with a given priority to the collection.

  • peekmin(): Returns the item with the highest priority.

  • removemin(): Removes and returns the item with the highest priority.

• Simplified Supported operations:

  • insert(n): add n to heap

  • peekmin(): return the smallest integer

  • removemin(): remove and return the smallest integer

Heaps: Implementation Details

• Representing a heap using a Python list (array).

  • Encoding a tree structure in an array: Root at index 0. The left child of an index $i$ is at $2i + 1$, and the right child is at $2i + 2$.

  • A list is heap-sorted if its corresponding binary tree is heap-sorted.

Implementation: Class HeapPQ

• The root is at index 0

• The left child of an index $i$ is located at $2i + 1$

• The right child of an index $i$ is located at $2i + 2$

• A list is heap-sorted if its corresponding binary tree is heap-sorted.

• __init__(self) : Initializes the heap with an empty list called _entries

• _len_(self): Returns the number of entries in the heap.

• _parent(self, i): Returns the parent index for a given tree node index $i$, calculated as $(i - 1) // 2$. Integer division // is used.

• _left(self, i): Returns the index of the root of the left child subtree for a given tree node index $i$, calculated as $2*i + 1$

• _right(self, i): Returns the index of the root of the right child subtree for a given tree node index $i$, calculated as $2*i + 2$

• _children(self, i): Returns an iterable containing only the left and right child subtree root indices for a given index.

Heaps: peekmin

• Accessing the minimum element in a min-heap.

• peekmin(self): Returns the element at the root of the heap, which is self._entries[0].

• Running time: $O(1)$, as it is a direct access.

Heaps: insert

• Maintaining heap properties during insertion:

  • Completeness

  • Heap order

• To maintain heap order, swaps may be needed to move the new element up the tree.

• Running time: $O(log n)$.

Heaps: removemin

• Maintaining heap properties during removal:

  • Completeness

  • Heap order

• The process involves:

  • Replacing the root (minimum element) with the last element in the heap.

  • Reducing the size of the heap by one.

  • "Down-heaping" to restore heap order.

• Running time: $O(log n)$.

Heaps: Implementation code

• removemin(self):

  • $L = self._entries$: References the internal list of entries.

  • $item = L[0].item$: Stores the item at the root to be returned.

  • $L[0] = L[-1]$: Moves the last item in the list to the root.

  • L.pop(): Removes the last item (which was moved to the root).

  • self._downheap(0): Calls the _downheap method to restore heap order starting from the root.

  • return item: Returns the original minimum item.

• _downheap(self, i):

  • $L = self._entries$: References the internal list of entries.

  • children = self._children(i): Gets the indices of the children of the current node.

  • If children:

    • min_child = min(children, key = lambda x: L[x]): Finds the child with the smallest key.

    • If L[i] > L[min_child]:

      • self._swap(i, min_child): Swaps the current node with the smallest child.

      • self._downheap(min_child): Recursively calls _downheap on the swapped child to continue restoring heap order.

Priority Queues: Comparison

Building a Heap from a List

• Naive approach: insert items one by one into a HeapPQ object, which takes $O(n log n)$ time.

• A more efficient approach: Heapifying a list in linear time.

Heapify via Upheap

• Heap-ordering a list in-place by upheaping each node from left to right, level by level, resulting in a heap at the end.

Heapify via Downheap

• Heap-ordering a list in-place by downheaping each node from right to left, level by level, resulting in a heap at the end.

Heapify via Downheap: Running Time

• The _heapify method iterates in reverse through the array and calls the _downheap method on each element.

• def _heapify(self):

  • for i in reversed (range(len(self))):

    • self._downheap(i)

    • We only need to iterate through the left half of the array in reverse!

• A list can be heapified in linear time: $O(n)$.

Change Priority

• Given an item in the heap and a new priority:

  1. Change the priority of the entry that holds the item.

  2. Call upheap or downheap with the index of the entry to ensure heap-ordering holds after altering priority.

• This would only take $O(log n)$ time.

• Implement with a dictionary. This maps items to array indices so that we know where the entry for a given item is located in the array. This dictionary must be updated whenever an item is inserted into the heap or a swap is made, to ensure correctness.

• Example: change priority("Ed", 0)

  1. Look up index of “Ed” in item map; find entry.

  2. Change priority of entry

  3. Call upheap on entry

• Note that item map must be updated whenever swaps occur.

Heapsort

• Given a list of items, we can sort the items using a heap:

  1. Heapify the list – $O(n)$ time

  2. Repeatedly remove the minimum element until the heap is empty

• The items will be removed in sorted order!

• Heapsort is $O(n log n)$ .

Heapsort Implementation Details

• Instead of calling removemin, we can:

  • Swap the min element with the last heap index.

  • Decrement the internal size of the heap.

  • Call downheap on index 0.

  • Repeat until the internal size of the heap is 1.

• When using a min heap, this yields a reverse sorted list. Therefore, using this process with a max heap would be faster because we can avoid this reverse operation!

• Note: In-place heapsort is $O(n log n)$ because we still call downheap (0) $O(n)$ times. It is also not stable.

Heaps: Summary