CS146 Data Structures and Algorithms
Part II: Sorting and Order Statistics Chapter 6: Heapsort
L6.1
Sorting Algorithm
• Insertion sort :
§ In place: only a constant number of elements of the
input array are even sorted outside the array. • Merge sort :
§ not in place.
• Heap sort : (chapter 6)
§ Sorts n numbers in place in O(n lgn)
L6.2
Sorting Algorithm
• Quick sort : (chapter 7)
§ worst time complexity O(n2)
§ Average time complexity O(n lg n)
• Decision tree model : (chapter 8) § Lower bound O (n lg n)
§ Counting sort
§ Radix sort
• Order statistics
L6.3
Sorting Revisited
• So far we’ve talked about two algorithms to sort an array of numbers
§ What is the advantage of merge sort?
o Answer: O(n lg n) worst-case running time
§ What is the advantage of insertion sort?
o Answer: sorts in place
o Also: When array “nearly sorted”, runs fast in practice
• Next on the agenda: Heapsort
§ Combines advantages of both previous algorithms
L6.4
6.1 Heaps
• A heap can be seen as a complete binary tree: 16
14
10
8793
241
§ What makes a binary tree complete? § Is the example above complete?
L6.5
Heaps
• A heap can be seen as a complete binary tree: 16
14
10
8793
1
2411111
§ The book calls them “nearly complete” binary trees; can think of unfilled slots as null pointers
L6.6
Heaps
• In practice, heaps are usually implemented as arrays:
16
14 8793
241
10
16
14
10
8
7
9
3
2
4
1
A==
L6.7
Heaps
• To represent a complete binary tree as an array: § The root node is A[1]
§ Node i is A[i]
§ The parent of node i is
o A[i/2] (note: integer divide) § The left child of node i is
o A[2i]
§ The right child of node i is
o A[2i + 1] A==
16
14 8793
241
10
16
14
10
8
7
9
3
2
4
1
L6.8
Heaps (Binary heap)
• The binary heap data structure is an array object that can be viewed as a complete tree.
Parent(i)
return ë û
Left(i)
return 2i
Right(i)
return 2i+1
i/2
L6.9
Referencing Heap Elements
• So…
Parent(i) { return ëi/2û; } Left(i) { return 2*i; } right(i) { return 2*i + 1; }
• An aside: How would you implement this most efficiently?
§ Trick question, I was looking for “i << 1”, etc. § But, any modern compiler is smart enough to do
this for you (and it makes the code hard to follow)
L6.10
The Heap Property
• Heaps also satisfy the heap property: A[Parent(i)] 3 A[i] for all nodes i > 1
§ In other words, the value of a node is at most the value of its parent
§ Where is the largest element in a heap stored?
L6.11
Heap Height
• Definitions:
§ The height of a node in the tree = the number of
edges on the longest downward path to a leaf § The height of a tree = the height of its root
• What is the height of an n-element heap? Why?
• This is nice: basic heap operations take at most time proportional to the height of the heap
L6.12
The Heap Property
• Max-heap:A[Parent(i)]3A[i]
• Min-heap:A[Parent(i)]≤A[i]
• The height of a node in a tree: the number of edges on the longest simple downward path from the node to a leaf.
• The height of a tree: the height of the root
• The height of a heap: O(lg n).
L6.13
Pop Quiz
1. What are the minimum and maximum numbers of elements in a heap of height h ?
• There is a most 2h+1 – 1 vertices in a complete binary tree of height h. Since the lower level need not be filled we may only have 2h vertices.
L6.14
Pop Quiz
2. Show that an n-element heap has height (lg n)
• Since the height of an n-element heap must satisfy that 2h £ n £ 2h+1-1 < 2h+1.
• Wehave h£lgn