Design and Analysis of Algorithms

758 Design and Analysis of Algorithms

it. Thus w

j

>

1

2

C. Since the weights have been rearranged by greedy in non-increasing order, the

weights which have been added are also greater than

1

2

C. Thus

M

>

1

2

C.

2. Sort the jobs in non-decreasing order of fi

nish times, so that e

1

≤ e

2

≤ ... ≤ e

n

, and consider the jobs in

order, adding each job to the list of jobs to be actually carried out, if it does not start before the fi nish

time of the last job added.

Algorithm E.2.12 Huffman(c)

1 Analysis:

2 n ←

| c |; [ Q is the Binary Heap ]

3 Q ←

c; [ O(n) BuildHeap ]

4 for i ←

1 to n – 1 do

5 [ O(n) ]

6 z ←

Allocate-node();

7 x ←

Extract-Min( ...