Administrivia
Lectures start at 10:00
Homework 1 due May 5
Use Moodle for questions, clarifications, etc.
Reading: Chapters 3, 4
Last time: pseudocode, sorting, incremental algorithms,
divide-and-conquer, recurrences
Today: asymptotic notation, important functions, solving
recurrences
Administrivia
Lectures start at 10:00
Homework 2 due May 12
Use Moodle for questions, clarifications, etc.
Reading: Chapters 4, 5
Last time: asymptotic notation, important functions, solving
recurrences
Today: HeapSort
The Max Heap Data Structure
The (maximum, binary) heap data structure is an array that
can be viewed as a nearly complete binary tree:
16,14,10,8,7,9,3,2,4,1
If A is the array, A[1] contains the root of the tree
Level-by-level traversal of the tree gives us the array (heap)
Given an index i in the array we can easily compute the
parent, the left child, and the right child of A[i]
Parent(i)
return bi/2c
Left(i)
return 2i
Right(i)
return 2i + 1
The Max Heap Data Structure
16,14,10,8,7,9,3,2,4,1
Note that Left, Right, Parent can be implemented very
efficiently by shifting, rather than multiplication.
The max heap property: A[Parent(i)] A[i]
Then the largest element is in the root
Viewing a heap as a tree, the height of a node in a heap is
the number of edges on the (longest) node-to-leaf path
The height of the heap is height of its root
The height of a heap with n elements is ⇥(lg n)
Maintaining a Heap
MaxHeapify: manipulating and maintaining max-heaps
Before MaxHeapify A[i] may be smaller than its children
Assume that left and right subtrees of i are max-heaps
There are no violations of max-heap property within the left
and right subtrees; the only violation within the subtree
rooted at i could be between i and its children
After MaxHeapify subtree rooted at i is a max-heap
Maintaining a Heap: MaxHeapify
MaxHeapify(A, i)
l Left(i)
r Right(i)
if l A[heapsize] and A[l] > A[i]
largest l
else largest i
if r A[heapsize] and A[r ] > A[i]
largest r
if largest6= i
Swap(A[largest], A[i])
MaxHeapify(A, largest)
MaxHeapify
Compare A[i], A[Left(i)] and A[Right(i)]
If necessary, swap A[i] with the larger of the two children to
preserve heap property
Continue this process of comparing and swapping down the
heap, until subtree rooted at i is max-heap
If we hit a leaf, then the subtree rooted at the leaf is trivially
a max-heap
What’s the runtime of MaxHeapify in terms of n, the number of
nodes in the subtree rooted at A[i]?
The height of the subtree rooted at A[i] is ⇥(lg n), as the
heap is nearly complete binary tree
MaxHeapify does constant amount of work on each level
(compare 3 elements, possibly swap 2 of them)
This results in O(lg n) work in total
Making a Heap
Given an array with n integers, make a heap
BuildMaxHeap(A, n)
heapsize n
for i bi/2c downto 1
MaxHeapify(A, i)
4,1,3,2,16,9,10,14,8,7
Correctness of BuildMaxHeap
BuildMaxHeap(A, n)
heapsize n
for i bi/2c downto 1
MaxHeapify(A, i)
Loop invariant: At start of every iteration of for loop, each
node i + 1, i + 2, . . . n is root of a max-heap.
Initialization: Each node bn/2c + 1, bn/2c + 2, . . . n is a leaf,
which is the root of a trivial max-heap. Since i = bn/2c before
the first iteration of the for loop, the invariant is initially true.
Maintenance: Children of node i are indexed higher than i, so
by loop invariant, they are both roots of max-heaps. Correctly
assuming that i + 1, i + 2, . . . n are all roots of max-heaps,
MaxHeapify makes node i a max-heap root. Decrementing
i reestablishes loop invariant at each iteration.
Termination: When i = 0, the loop terminates. By loop
invariant, each node, notably node 1, is root of a max-heap.
Runtime of BuildMaxHeap
BuildMaxHeap(A, n)
heapsize n
for i bi/2c downto 1
MaxHeapify(A, i)
There are n/2 calls to MaxHeapify, which runs in time O(lg n),
so O(n lg n)
Tighter analysis:
Time to run MaxHeapify is linear in the height of the node
it’s run on, and most nodes have small heights
More careful analysis will give us O(n) time
HeapSort
HeapSort(A, n)
BuildMaxHeap(A, n)
for i n downto 2
Swap(A[1], A[i])
heapsize
MaxHeapify(A, 1)
1,8,3,2,7,5,4,6,9
HeapSort Properties
Runtime:
BuildMaxHeap takes O(n lg n)
MaxHeapify takes O(lg n) and is called n times
Total runtime: O(n lg n)
MergeSort also runs in O(n lg n) time, but needs additional
memory, while HeapSort sorts in-place
HeapSort is a good example of the utility of appropriate data
structures
