Data Structures and Algorithms (H) Lecture 4 Notes

HeapSort

Introduction

The idea behind HeapSort is to find the largest element and move it to the end of the array. Then we repeat this process with remaining elements until the array is sorted. This idea is similar to the SelectionSort, but SelectionSort compares lots of elements to find the largest, while the HeapSort store knowledge gained from these comparisons for future use. This make the HeapSort very efficient on both runtime and storage, and it also sorts arrays in place. More specifically, we use a clever data structure, a heap to achieve this.

Heap

A heap is essentially an array imagined as being a binary tree. The elements are arranged row by row from left to right. For example, the array can be viewed as a heap like this We navigate through the array/imaginary tree using these operations: - Max-heap property: for every node other than the root, the parent is no smaller than the node, i.e., . In a max-heap, the root always stores a largest element, this is exactly what we wants for the sorting algorithm. - Min-heap property, for every node other than the root, the parent is no larger than the node, i.e., .

Procedures Needed for the Algorithm

1. Build-Max-Heap: produces a max-heap from an unordered array.
2. Max-Heapify: maintains the max-heap property once the maximum (the root element) has been removed.
3. HeapSort: sorts an array in place.

We also need to introduce a new variable A.heap-size which indicates how many elements of are stored in a heap. Decreasing A.heap-size by 1 effectively removes the last element from the heap. There are analogous operations for min-heaps.

Max-Heapify(A,i)

First we assumes subtrees and are max-heaps, but max-heap property might be violated in root of subtree at . Then to restore the max-heap property at , we lets the value at “float down”, if necessary. At the end of Max-Heapify the subtree at is a max-heap. To do this, we proceed as follows: - Compare with all existing children, and - if the largest child is larger than , swap and recurse on child.

Runtime

To figure out the runtime of Max-Heapify, we need to first define the height of the node in a tree.

Definition: Height of Tree Nodes

The height of a tree node is the longest number of simple downward edges from the node to a leaf.

We know that Max-Heapfity takes constant time on each level. Then the running time of Max-Heapify on a node of height is . We claim that the height of a heap, i.e. the height of the root, is at most . Proof: the number of elements in a heap of height is - doubling on each level - at least 1 node on the last level - hence in total at least we have So the size and height are related as So the runtime is .

Correctness

We prove the correctness by induction on the height: - Base case: height is 0, which means we are on a leaf, this is trivial. - Inductive case: assume the algorithm is work for height and show it works for . Then the algorithm swaps with the larger between and (if any) and one subtree was already a heap and the other will be by inductive hypothesis.

Build-Max-Heap(A,n)

The idea is to use Max-Heapify repeatedly to create a heap. Since Max-Heapify assumes and are heaps, so we need to construct the heap bottom-up.

Tip

Nodes in are all leaves. Since leaves are already max-heaps, so no work is required on them.

A example run of this algorithm on the following initial array:

Correctness

We prove the correctness of Build-Max-Heap by using loop invariant. - Loop invariant: At the start of each iteration of the for loop, each node is the root of a max-heap. - Initialization: true for leaves . - Maintenance: by loop invariant, all children of are roots of max-heaps as their indexes are larger than . Then Max-Heapify(A,i) turns the subtree at into a max-heap. - Termination: the loop terminates at , hence node 1 is the root of a max-heap.

Runtime

Since all nodes have height at most , and every call to Max-Heapify takes time . The Build-Max-Heap calls Max-Heapify times. So the total time is at most But this is not a tight bound, though it is sufficient for our discussion. The runtime can be improved to since most of the nodes have a small height.

Refined Runtime Analysis

The key observation is that most nodes in the tree have small height. We can show that there are at most nodes of height . We prove this by induction:

A better bound for the Build-Max-Heap can then be calculated as as the infinite series of is . Two important inequalities we used: - for , from this we get for , because . - for .

HeapSort

With all the procedures introduces above, we can now describe the idea of the HeapSort as follows: - Build a max-heap, s.t. the root contains largest element. - Swap the root with the last element of the heap/array. - Discard the last element from the heap by reducing the size of the heap by 1. - Call Max-Heapify(A,1) to restore heap property at the root. The pseudocode goes as follows: The runtime will then be

Correctness of HeapSort

• Loop invariant: At the start of each iteration of the for loop of line 2-5, the subarray is a max-heap containing the smallest elements of , and the subarray contains the largest elements of and is sorted.
• Initialization: The subarray is empty, the invariant trivially holds.
• Maintenance: is the largest element in and it is smaller than the elements in . When we put it in the -th position, then contains the largest elements, sorted. Decreasing the heap size and calling Max-Heapify turns into a max-heap. Decrementing sets up the invariant for the next iteration.
• Termination: After the loop . This means that is sorted and is the smallest element in the array, which makes the array sorted.