Introduction
1
Sorting
A universal problem!
Many applications often incorporate sorting
There is a wide variety of sorting algorithms, and they use rich set of techniques.
2
Sorting algorithm
Insertion, Bubble, Selection sorts:
Non-recursive
In place: only a constant number of additional storage locations (for local variables) are used outside the array.
Merge sort :
Recursive; Not in place.
Heap sort : (Chapter 6)
Non-recursive
Sorts n numbers in place in O(nlgn)
3
Sorting algorithm
Quick sort : (chapter 7)
Recursive
In place
Worst time complexity O(n2); Average time complexity O(n logn)
Fastest general purpose sorting algorithm
Linear sorting algorithms : (chapter 8)
Counting sort
Radix sort
Bucket Sort
Heapsort
Ch. 6 Reading Assignments
All of the chapter (make sure you understand the Loop Invariant correctness proof of BUILD-MAX-HEAP on p. 157 but omit its mathematical proof of complexity on p.159)
5
6.1 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
6
Heap property
Max-heap : A [parent(i)] A[i]
Min-heap : A [parent(i)] ≤ A[i]
The height of a node in a tree: the number of edges on the longest downward path from the node to a leaf.
The height of a tree: the height of the root
The height of a heap: floor(lg n)=O(lg n).
7
Basic algorithms on max heap
Max-Heapify algorithm
Build-Max-Heap algorithm
Heapsort algorithm
Heap-Extract-Max algorithm
Heap-Maximum algorithm
Max-Heap-Increase-Key algorithm
Max-Heap-Insert algorithm
8
6.2 Maintaining the heap property
Max-Heapify is an important subroutine for manipulating heaps. Its inputs are an array A and an index i in the array. When Heapify is called, it is assumed that the binary trees rooted at LEFT(i) and RIGHT(i) are heaps, but that A[i] may be smaller than its children, thus violating the max heap property.
9
Max-Heapify (A, i)
1 l =2i
2 r =2i+1
3 if l ≤ heap-size(A) and A[l] > A[i]
4 then largest = l
5 else largest = i
6 if r ≤ heap-size[A] and A[r] > A[largest]
7 then largest = r
8 if largest i
9 then swap A[i] and A[largest]
10 Max-Heapify (A, largest)
Thinking Assignment: How about Min-Heapify?
10
Max-Heapify(A,2)
heap-size[A] = 10
Max-Heapify Complexity
It has to be O(height) – why?
Height of a heap is O(lgn)
So Max-Heapify is O(lgn)
Alternately
What is the base case?
What are the recurrence relations?
These can be solved to show T(n)=O(lgn)
Thinking Assignment: Try it!
11
12
6.3 Building a heap
Build-Max-Heap(A)
1 heap-size(A) = length(A)
2 for i = heap-size(A)/2 downto 1
3 Max-Heapify(A, i)
Why does this loop start from length(A)/2 ?
Why does the loop not go from 1 to heap-size(A)/2 ?
13
Build-Max-Heap
14
15
16
What is Build-Max-Heap’s complexity?
O(nlgn) is a good estimate – why?
But a tighter upper bound can be found: Build-Max-Heap is actually O(n) – linear!
If you want to know why, look at the next slide and read the text p. 159 (optional)
17
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
18
6.4 The Heapsort algorithm
Heapsort(A)
1 Build-Max-Heap(A)
2 for i = length(A) down to 2
3 swap A[1] and A[i]
4 heap-size[A] = heap-size[A] -1
Max-Heapify(A,1)
Thinking Assignment:
Does this algorithm sort in ascending order?
Why is its worst-case complexity O(nlgn)?
What is its best case complexity? For what kind of input?
19
The operation of Heapsort
20
Analysis: O(n logn)
21
Priority queues
The heap data structure is not only used in sorting but also in priority queues. A priority queue is a data structure that maintains a set S of elements, each with an associated value call a key. Priority queues has many applications. A max (or min) priority queue should at least support the following operations:
Insert (S, x) O(log n)
Maximum/Minimum (S) O(1)
Extract-Max/Min (S) O(log n)
Increase-Key (S, x, k) O(log n)
Decrease-Key (S, x, k) O(log n)
22
Two Heap Operations
Heap-Extract-Max(A)
1 if heap-size[A] < 1
2 then error “heap underflow”
3 max = A[1]
4 A[1] =A[heap-size(A)]
5 heap-size(A) = heap-size(A) - 1
6 Max-Heapify (A, 1)
return max
Heap-Maximum(A)
1 return A[1]
Thinking Assignment: Write Heap-Extract-Min(A)
23
Max-Heap-Increase-Key (A, i, key)
1 if key < A[i]
2 then error “new key is smaller than current key”
3 A[i] = key
4 while i > 1 and A[Parent(i)] < A[i]
5 swap A[i] and A[Parent(i)]
i = Parent(i)
Thinking Assignment:
What is this algorithm’s complexity?
Write Max-Heap-Decrease-Key (A, i, key)
Write Min-Heap-Increase-Key (A, i, key)
Min-Heap-Decrease-Key (A, i, key)
24
Heap-Increase-Key
25
Max-Heap-Insert(A, key)
1 heap-size(A) = heap-size(A) + 1
2 A[heap-size(A)] = -∞
Max-Heap-Increase-Key (A, heap-size(A), key)
Thinking Assignment: Write Min-Heap-Insert(A, key)
26
Thinking Assignments
Min-Heapify
Build-Min-Heap
Heapsort procedure using a Min heap
Heap-Extract-Min
Heap-Minimum
Min-Heap-Decrease-Key
Min-Heap-Insert
Max-Heap-Decrease-Key
Min-Heap-Increase-Key
ë
û
i
/
2
c
n
T
or
n
T
n
T
c
case
base
T
+
Q
+
£
=
Q
=
)
3
2
(
)
1
(
)
3
2
(
)
(
)
1
(
)
(
On n(log )
? We can find a
tighter upper bound!
0
1
lg
1
1
lg
1
1
)(
2
)(
2
)(
))(*)((#
lg)(
2
lg
h
h
n
h
h
n
h
h
hO
n
hO
n
nT
chOhheightatnodesof
orithmathefornT
hheightatnodes
n
and
nheighthasheapelementn
nonTsonOhO
n
nT
nOnO
h
nOSo
x
x
kxbecause
h
and
h
nOhO
n
But
h
h
h
h
k
k
h
h
h
h
h
h
)(),()(
2
)(
)()2*()
2
(
)
)1(
( 2
2
)
2
()(
2
0
1
0
0
2
0
00
1
ë
û
ë
û
ë
û
å
å
å
¥
=
+
=
+
=
+
ú
ú
ù
ê
ê
é
<
ú
ú
ù
ê
ê
é
=
+
=
ú
ú
ù
ê
ê
é
-
0
1
lg
1
1
lg
1
1
)
(
2
)
(
2
)
(
)
)
(
*
)
((#
lg
)
(
2
lg
h
h
n
h
h
n
h
h
h
O
n
h
O
n
n
T
c
h
O
h
height
at
nodes
of
orithm
a
the
for
n
T
h
height
at
nodes
n
and
n
height
has
heap
element
n
·
? We can find a tighter upper bound!
_1265544168.unknown
_1265551124.unknown
_1265551281.unknown
_1265551418.unknown
_1284272062.unknown
_1265551129.unknown
_1265550912.unknown
_1063712803.unknown
_1265544113.unknown
_925574761.unknown
(
)
n
o
n
T
so
n
O
h
O
n
n
T
n
O
n
O
h
n
O
So
x
x
kx
because
h
and
h
n
O
h
O
n
But
h
h
h
h
k
k
h
h
h
h
h
h
=
=
ú
ú
ù
ê
ê
é
<
=
=
-
=
=
=
ú
ú
ù
ê
ê
é
å
å
å
å
å
å
¥
=
+
¥
=
¥
=
¥
=
¥
=
¥
=
+
)
(
),
(
)
(
2
)
(
)
(
)
2
*
(
)
2
(
)
)
1
(
(
2
2
)
2
(
)
(
2
0
1
0
0
2
0
0
0
1
_1265544168.unknown
_1265551599.unknown
_1283838232.unknown
_1284272265.unknown
_1265551681.unknown
_1265551168.unknown
_1063712803.unknown
_1265544113.unknown
_925574761.unknown
/docProps/thumbnail.jpeg