CS计算机代考程序代写 data structure algorithm Introduction

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