[SOLVED] CS algorithm CSCI 4041

CSCI 4041
Discussion Section Notes
[email protected]

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 nodes parent: i/2
Index of a nodes left child: 2i
Index of a nodes 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