CS代考计算机代写 algorithm Analysis of Algorithms
Analysis of Algorithms
V. Adamchik CSCI 570
Lecture 3 University of Southern California
Heaps
Reading: chapter 3
Amortized Analysis
In a sequence of operations the worst case does not necessarily occur in each operation …
Therefore, a traditional worst-case per operation analysis can give overly pessimistic bound.
When same operation takes different times, how can we accurately calculate the runtime complexity?
The Aggregate Method
The aggregate method computes the upper bound T(n) on the total cost of n operations.
The amortized cost of an operation is given by 𝑇(𝑛) 𝑛
In this method each operation will get the same amortized cost, even if there are several types of operations in the sequence.
Review Questions
Review: Exercise 2
The Accounting Method
The accounting method (or the banker’s method) computes the individual cost of each operation.
We assign different charges to each operation; some operations may charge more or less than they actually cost.
The amount we charge an operation is called its amortized cost.
Discussion Problem
You have a stack data type, and you need to implement a FIFO queue. The stack has the usual POP and PUSH operations, and the cost of each operation is 1. The FIFO has two operations: ENQUEUE and DEQUEUE.
We can implement a FIFO queue using two stacks. What is the amortized cost of ENQUEUE and DEQUEUE operations?
Heap and Priority Queue for
Solving Optimization Problems
Binary min-Heap
A binary heap is a complete binary tree which satisfies the heap ordering property.
1. Structure Property
2. Ordering Property
2 43
948
0
1
2
3
4
5
6
7
Consider k-th element of the array,
• its left child is located at 2*k index
• its right child is located at 2*k+1 index
• its parent is located at k/2 index
2 43
978
insert (tree reps)
2 43
978
insert (array reps)
0
1
2
3
4
5
6
7
Discussion Problem 1
The values 1, 2, 3, . . . , 63 are all inserted (in any order) into an initially empty min-heap. What is the smallest number that could be a leaf node?
deleteMin (tree reps)
2 43
978
deleteMin (array reps)
2 43
978
0
1
2
3
4
5
6
7
Discussion Problem 2
Suppose you have two binary min-heaps, A and B, with a total of n elements between them. You want to discover if A and B have a key in common. Give a solution to this problem that takes time O(n log n). Do not use the fact that heaps are implemented as arrays.
36
5 8 12 7
7 9 10 13 15
Build a Heap by Insertion
Given an array – turn it into a heap.
7, 3, 8, 1, 4, 9, 4, 10, 2, 0
Build a Heap in O(n) Heapify: 7, 3, 8, 1, 4, 9, 4, 10, 2, 0
Complexity of heapify
We will count the max number of swaps at each level
height
# of nodes
# of swaps
0
1
2
…
…
…
h-1
Complexity of heapify
Discussion Problem 3
How would you sort using a binary heap? What is it runtime complexity?
Run delMin n-times
O(n log n)
1 26
3478
in-place nonstable
HEAPSORT
0
1
2
3
4
5
6
7
1
2
6
3
4
7
8
2
3
6
8
4
7
1
3
4
6
8
7
2
1
4
8
6
7
3
2
1
Discussion Problem 4
How would you merge two binary min-heaps? What is it runtime complexity?
Discussion Problem 5
Devise a heap-based algorithm that finds the k-th largest element out of n elements. Assume that n > k. What is its runtime complexity?
1 26
3478
decreaseKey
