CSCI 4041
Discussion Section Notes
mo000007@umn.edu
Binary Tree
● Every node contains following parts:
○ Key (value) of the node
○ Pointer to Left child
○ Pointer to Right child
● Subtree: a smaller tree consisting of all of its descendants inside a tree.
● Leaf nodes: the nodes that have no children, which means the leaf nodes are always at the bottom of the tree.
● Height: the longest path from root node to any leaf node in the tree.
2
Heaps
The binary heap is a nearly complete binary tree; completely filled on all levels except possibly the lowest (filled from the left up to a point).
Array representation of a binary heap:
● Index of a node’s parent: ⌊i/2⌋
● Index of a node’s left child: 2i
● Index of a node’s right child: 2i + 1
Eg. index of 8: 4
index of 14(parent): ⌊4/2⌋ = 2 index of 2(left child): 2*4 = 8 index of 4(right child): 2*4+1 = 9
3
Heap Property
● Max-heap: the value of a node is at most the value of its parent
○ the root is the largest element
○ A[parent(i)] ≥ A[i]
● Min-heap: the opposite of max-heap
○ the root is the smallest element
○ A[parent(i)] ≤ A[i]
Maintaining max/min heap property:
If max/min property is violated – A[i] is smaller/greater than its children – swap the values
4
Max-Heapify
Max-Heapify(A, 2)
largest
A[i]
A[l]
Final state
A[r]
A[i]
A[l]
A[r]
largest
● Find the largest among A[i], A[l] and A[r] (the green nodes)
● Swap the A[largest] with A[i] (largest is the index here)
● Recursive call on the largest until it reaches the leaf nodes
5
Build Max Heap
page: 154, 157
6
Build Max Heap
1 2 3 4 5 6 7 8 9 10
Green nodes: largest (for each recursive call) Max-heapify on Red subtree
Max heap
7
Build Max Heap Exercise:
Illustrate the operation of MAX-HEAPIFY(A, 2) on the array A = [27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0]
Write code for BUILD-MAX-HEAP and MAX-HEAPIFY. Then build a max heap on [5, 13, 2, 25, 7, 17, 20, 8, 4]
8
Build Max Heap Exercise:
Illustrate the operation of MAX-HEAPIFY(A, 2) on the array A = [27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0]
[27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0] [27, 17, 10, 16, 13, 3, 1, 5, 7, 12, 4, 8, 9, 0] [27, 17, 10, 16, 13, 9, 1, 5, 7, 12, 4, 8, 3, 0]
9
HeapSort
Runtime: O(n lg n) page: 160
10
HeapSort
A = [9, 8, 15, 25, 20, 5, 11, 2, 1] After line 1:
After line 3 and 4 (i=8):
1
20
8 9 5 11
2 25
Heap Size
A = [1, 20, 15, 8, 9, 5, 11, 2, 25] After line 5 (max-heapify):
A = [20, 9, 15, 8, 1, 5, 11, 2, 25]
25
15 i=7:
A = [2, 9, 15, 8, 1, 5, 11, 20, 25]
20
15
Heap Size
8 9 5 11
21
A = [25, 20, 15, 8, 9, 5, 11, 2, 1]
(max-heapify):
A = [15, 9, 11, 8, 1, 5, 2, 20, 25]
i=6: Heap Size
A = [2, 9, 11, 8, 1, 5, 15, 20, 25] (max-heapify):
A = [11, 9, 5, 8, 1, 2,15, 20, 25]
11
Reference
Introduction to Algorithms, Third Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein.
12