# 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