Content

Trees Heap Fundamentals Modifying Heaps Priority Queue Heapify and Heapsort <- Go Back

EECS 281: Data Structures and Algorithms

Section 07

Heaps, Priority Queues, and Heapsort

University of Michigan at Ann Arbor

Last Edit Date: 06/05/2023

Disclaimer and Term of Use:

1. We do not guarantee the accuracy and completeness of the summary content. Some of the course material may not be included, and some of the content in the summary may not be correct. You should use this file properly and legally. We are not responsible for any results from using this file

2. This personal note is adapted from Professor Marcus Darden and David Paoletti. Please contact us to delete this file if you think your rights have been violated.

3. This work is licensed under a Creative Commons Attribution 4.0 International License.

---

Trees

i. Introduction

A graph consist of nodes (sometimes called vertices) connected together by edges.

Each node can contian some data.

A tree is:

• a connected graph (nodes + edges) without cycles

• a graph where any 2 nodes are connected by a unique shortest path (the two defenitions are equivalent)

In a directed tree, we can identify child and parent relationships between nodes.

In a binary tree, a node has at most two children.

ii. Types of Trees

• (Simple) Tree

  • Acyclic connected graph

  • Considered undirected

• Rooted Tree

  • A simple tree with a selected node (root)

  • All edges are directed away from root

Any node could be selected as root.

iii. Tree Terminology

• Root: the “topmost” node in the tree
• Parent: Immediate predecessor of a node
• Child: Immediate successor of a node
• Siblings: Children of the same parent
• Ancestor: parent of a parent (closer to root)
• Descendent: child of a child (further from root)
• Internal node: a node with children
• External (Leaf) node: a node without children

v. Data Representation

template <class Item>
sturct Node {
    Node *left;
    Node *right;
    Item item;
}

• A node contains some information, and points to its left child node and right child node

  • Can also include a pointer for parent node

  • Can include pointers to 3 children, or a vector of pointers

• Efficient for moving down a tree from parent to child

vi. Trees are Recursive Structures

Any subtree is just as much a "tree" as the original!

v. Tree Properties

• Height

  • height(empty) = 0

  • height(node) = max(height(left_child), height(right_child)) + 1

• Size

  • size(empty) = 0

  • size(node) = size(left_child) + size(right_child) + 1

• Depth

  • depth(empty) = 0

  • depth(node) = depth(parent) + 1

Heap Fundamentals

i. Complete (Binary) Trees

Binary tree: every node has 2 or fewer children

Complete binary tree: every level, except possibly the last, is completely filled, and all nodes are as far left as possible

ii. Data Representation: Complete Binary Trees

• A complete binary tree can be stored efficiently in a growable array (i.e. vector) by indexing nodes according to level-ordering.

  • The completeness ensures no gaps in the array

  • We index starting at 1 because it makes some math work out better

  • To gracefully achieve 1-based indexing with a 0-indexed vector, you can just add a dummy element position 0 and ignore it

• Given the index of a node at position $i$ in the tree, then

  • The index of $i$'s parent is: $(i - 1) / 2$

  • The index of $i$'s left child is: $2i + 1$

  • The index of $i$'s right child is: $2i + 2$

iii. Heap-Ordered Trees, Heaps

Heap-ordered: A tree is (max) heap-ordered if each node's priority is not greater than the priority of the node's parent.

A heap is a set of nodes with keys arranges ina complete heap-ordered tree, represented as an array.

Property: No node in a heap has a key larger than the root's key.

Heap: A heap has two crucial properties (representation invariants):

• Completeness

• Heap-ordering

iv. Executive Summary

Loose definition: data structure that gives easy access to the most extreme element (ex: maximum or minimum)

• "Max Heap": heap with largest element begin the "most extreme"

• "Min Heap": heap with smallest element being the "most extreme"

Heaps use complete (binary) trees as underlying structure, but are often implemented using arrays.

Modifying Heaps

Example: An Increasing Priority

Increase key at heap[8] from 2 to 35.

We use fixUp() to perform a bottom-up fix when the priority of an item in the heap is increased.

 1     void fixUp(Item heap[], int k) {
 2         while (k > 1 && heap[k / 2] < heap[k]) {
 3             swap(heap[k], heap[k / 2]);
 4             k /= 2;
 5         }
 6     }

• Pass index k of array element with increased priority

• Swap the node's key with the parent's key until:

  • the node has no parent (it is the root)

    OR

  • the node's parent has higher (or equal) priority key

Example: An Decreasing Priority

Decrease key at heap[2] from 18 to 3.

We use fixDown() to perform a top-down fix when the priority of an item in the heap is decreased.

 1     void fixDown(Item heap[], int heapsize, int k) {
 2         while (2 * k <= heapsize) {
 3             int j = 2;
 4             if (j < heapsize && heap[j] < heap[j + i]) ++j;
 5             if (heap[k] >= heap[j]) break;
 6             swap(heap[k], heap[j]);
 7             k = j;
 8         }
 9     }

• Pass index k of array element with decreased priority

• Exchange the key in the given node with the highest priority key among the node's children, moving down until:

  • the node has no children (leaf node)

    OR

  • the node has no children with a higher key

Priority Queue

i. Introduction

A priority queue is a data structure that supports three basic operations:

• push(): Insertion of a new item

• top(): Inspection of the highest priority item

• pop(): Removal of the item with the highest priority

PQ essential for upcoming algorithms (ex: shorest-path, Dijkstra's algorithm)

PQ useful for past and current algorithms (ex: heapsort, sorting in reverse order)

Priority queues are often implemented using heaps because insertion / removal operations have the same time complexity.

ii. Insertion

Insertion operation must maintain heap invariants: max (or min) element must be root

 1     void push(Item newItem) {
 2         heap[++heapsize] = newItem;
 3         fixUp(heap, heapsize);
 4     }

• Insert newItem into bottom of tree / heap (i.e. last element)

• newItem "bubbles up" tree swapping with parent while parent's key is less (use greater for min-heap)

iii. Deletion

Deletion operation can only remove root and must maintain heap invariants: max (or min) element must be root

 1     void pop() {
 2         heap[1] = heap[heapsize--];
 3         fixDown(heap, heapsize, 1);
 4     }

• Remove root element - results in disjoint heap

• Move the last element into the root position

• New root "sinks" down the tree swapping with highest priority child whose key is greater (less for min-heap)

iv. Complexity Analysis

Unordered array PQ

• $O(1)$ insertion of an item

• $O(n)$ inspection of top item

• $O(n)$ removal of top item

Sorted array PQ

• $O(n)$ insertion of an item

• $O(1)$ inspection of top item

• $O(1)$ removal of top item

Heap

• Efficient $O(\log n)$ insertion of an item using fixUp()

• $O(1)$ inspection of top item

• Efficient $O(\log n)$ removal of top item using fixDown()

• Must maintain heap property

Heapify and Heapsort

i. Heapify (build a heap)

• You could start wiht an empty vector, and add elements one at a time, keeping the heap property valid after each push()

  • Insert n elements, $O(\log n)$ for each push() produces $O(n \log n)$ time

  • Requires an extra vector, or $O(n)$ extra memory

• Sort in reverse order: $O(n \log n)$; $O(1)$ memory

• Instead, modify the given array: proceed from bottom to top or top to buttom, using fixDown() or fixUp()

  • 4 possibilities; two work and two do not

  • Those that work have different complexities

ii. Heapsort

Step 1: Swap 81 $\leftrightarrow$ 1 Step 2: Fix-down [1] ... [8] Step 3: Swap 18 $\leftrightarrow$ 2 Step 4: Fix-down [1] ... [7] Step 5: Swap 14 $\leftrightarrow$ 5 Step 6: Fix-down [1] ... [6] Step 7: Swap 9 $\leftrightarrow$ 2 Step 8: Fix-down [1] ... [5] Step 9: Swap 7 $\leftrightarrow$ 1 Step 10: Fix-down [1] ... [4] Step 11: Swap 18 $\leftrightarrow$ 2 Step 12: Fix-down [1] ... [3] Step 13: Swap 14 $\leftrightarrow$ 5 Step 14: Fix-down [1] ... [2]

Intuition: repeatedly relocate the highest-priority element from PQ to the back.

Easily implemented as an array; entire sort done in place.

 1     void heapsort(Item heap[], int n) {
 2         heapify(heap, n);
 3         for (int i = n; i >= 2; i--) {
 4             swap(heap[i], heap[1]);
 5             fixDown(heap, i - 1, 1);
 6         }
 7     }

Part 1: Transform unsorted array into heap (heapify)

Part 2: Remove the highest priority item from heap, add it to sorted sequence, and fix the heap, repeat.

Complexity Analysis

• Take the given n elements, convert into a heap

  • Bottom-up fixDown(), heapify takes $O(n)$ time

• Remove elements one at a time, filling original array from back to front

  • Swap element at top of heap with last unsorted: $O(1)$

  • fixDown() to bottom: each takes $O(\log n)$ time, n of them

• Total runtime: $O(n \log n)$

  • Requires no additional space

© Sample Academy