Com S 311 Section B Introduction to the Design and Analysis of Algorithms
Lecture One for Week 5
Xiaoqiu (See-ow-chew) Huang
Iowa State University
February 23, 2021
Priority Queues
We use the heap data structure to implement an efficient priority queue data structure.
A priority queue is a data structure for keeping a set S of elements, each associated with a value called a key.
A max-priority queue allows the following operations.
INSERT(S,k) inserts an element associated with the value k to S.
MAXIMUM(S) returns the largest value of elements in S.
EXTRACT-MAX(S) removes and returns the largest value of elements in S.
INCREASE-KEY(S,x,k) increases the value of element x in S to the new value k, which is supposed to be at least as large as the current value of x.
Implementation
Below we use a max-heap to implement a max-priority queue.
HEAP-MAXIMUM(A)
1 return A[1] // O(1) time
HEAP-EXTRACT-MAX(A)
1 if A.heap-size < 1
2 error ‘heap underflow’
3 max=A[1]
4 A[1] = A[A.heap-size]
5 A.heap-size = A.heap-size - 1 6 MAX-HEAPIFY(A, 1)
7 return max // O(lg n) time
HEAP-INCREASE-KEY(A, i, key)
1
2
3
4 while i > 1 and A[PARENT(i)] < A[i]
5 exchange A[i] with A[PARENT(i)]
6 i = PARENT(i) // O(lg n) time
ifkey
Example
lengthi: 12345
pricepi: 26789
Consider all decompositions of a rod of length 4.
(4, 8) denotes a decomposition into a piece of length 4 with price 8.
(1, 2)(3, 7) denotes a decomposition into a piece of length 1 with price 2 and a piece of length 3 with price 7.
The remaining decompositions are: (2, 6)(2, 6), (3, 7)(1, 2),
(1, 2)(1, 2)(2, 6), (1, 2)(2, 6)(1, 2),
(2, 6)(1, 2)(1, 2), and (1, 2)(1, 2)(1, 2)(1, 2)
An optimal decomposition < 4, 12 >= (2, 6)(2, 6) with r [4] = 12. That is, an optimal decomposition of the rod into two 2-inch pieces generates revenue p2 + p2 = 6 + 6 = 12.
Example
An optimal decomposition of a rod of length 5 is
< 5, 14 >= (1, 2)(2, 6)(2, 6), (2, 6)(1, 2)(2, 6), or (2, 6)(2, 6)(1, 2) with r[5] = 14.
Note that < 5, 14 >= (1, 2) < 4, 12 > or (2, 6) < 3, 8 >.
The first piece is of length 1, and the right-hand remainder of length 4 is an optimal decomposition of a rod of length 4, or the first piece is of length 2, and the right-hand remainder of length 3 is an optimal decomposition of a rod of length 3.
Note that < 3, 8 >= (1, 2)(2, 6) or (2, 6)(1, 2), but not (3, 7).
Also note that (2, 6)(3, 7) is a decomposition of a rod of length 5 = 2 + 3 with revenue 13 = 6 + 7, not an optimal one.
Recurrence for r[j]
For each j, 1 ≤ j ≤ n, define r[j] to be the maximum revenue of all
decompositions of a rod of length j.
Then r[n] is the revenue of an optimal decomposition of a rod of
length n. Assume that r[0] = 0.
Consider an optimal decomposition of a rod of length j with
revenue r[j].
This optimal decomposition consists of a first piece of length h, 1 ≤ h ≤ j, and a right-hand remainder of length j − h.
Recurrence for r[j]
Since the decomposition is optimal, the right-hand remainder is an optimal decomposition of a rod of length j − h and its revenue is r[j − h].
Thus, we have for some h, 1 ≤ h ≤ j,
< j , r [j ] >= (h, ph ) < j − h, r [j − h] >, and
r[j] = ph + r[j − h]. (1)
Define s[j] to be the size h of the first piece in an optimal decomposion of a rod of length j.
In our small example, we have
< 5, 14 >= (1, 2) < 4, 12 > for h = 1, and 14 = 2 + 12 with
p1 = 2, <4,12>=(2,6)<2,6>forh=2,and12=6+6withp2 =6.
Recurrence for r[j]
Note for each i, 1 ≤ i ≤ j, adding piece (i,pi) to an optimal decomposion < j − i , r [j − i ] > results in a decomposition of a rod of length j with revenue pi + r[j − i]. Because r[j] is the maximum revenue of all decompositions of a rod of length j, we have
r[j] ≥ pi + r[j − i] for all i, 1 ≤ i ≤ j. (2)
Combining (1) and (2) together, we have r[j] = max1≤i≤j(pi + r[j − i]). (3)
For each j from 1 to n, the recurrence (3) is used to compute the revenue of an optimal decomposition of a rod of length j.
EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
1 2 3 4 5 6 7 8 9
letr[0..n]ands[0..n]benewarrays r[0]=0
forj=1ton
q = negative infinity
for i = 1 to j
if q < p[i] + r[j-i]
q = p[i] + r[j-i]
s[j] = i
r[j] = q
print-cut-rod-solution(p, n)
1 (r, s) = EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
2 3 4
whilen>0
print (s[n], p[s[n]]) n = n – s[n]
Executing the Algorithm on the Example
lengthi: 12345
pricepi: 26789
r[1]=max{p1 +r[0]}=max{2+0}=2,
s[1] = 1,
r[2]=max{p1 +r[1],p2 +r[0]}=max{2+2,6+0}=6,
s[2] = 2,
r[3]=max{p1 +r[2],p2 +r[1],p3 +r[0]}=
max{2 + 6, 6 + 2, 7 + 0} = 8,
s[3] = 1,
r[4]=max{p1 +r[3],p2 +r[2],p3 +r[1],p4 +r[0]}=
max{2 + 8, 6 + 6, 7 + 2, 8 + 0} = 12,
s[4] = 2,
r[5]=max{p1 +r[4],p2 +r[3],p3 +r[2],p4 +r[1],p5 +r[0]}
= max{2 + 12, 6 + 8, 7 + 6, 8 + 2, 9 + 0} = 14,
s[5] = 1.
An optimal decomposition of a rod of length 5 is (1, 2)(2, 6)(2, 6).
EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
1 2 3 4 5 6 7 8 9
letr[0..n]ands[0..n]benewarrays r[0]=0
forj=1ton
q = negative infinity
for i = 1 to j
if q < p[i] + r[j-i]
q = p[i] + r[j-i]
s[j] = i
r[j] = q
print-cut-rod-solution(p, n)
1 (r, s) = EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
2 3 4
whilen>0
print (s[n], p[s[n]]) n = n – s[n]
Running Time of the Algorithm
Let a constant d > 0 be an upper bound on the cost of executing each line once in EXTENDED-BOTTOM-UP-CUT-ROD.
Each iteration of lines 5-8 is bounded from above by 4d, and the number of iterations is j. Thus, the cost of lines 4-8 is bounded from above by 4dj + d.
Each iteration of lines 3-9 is bounded from above by 3d + 4dj + d.
Running Time of the Algorithm
Thus, the running time of the algorithm is bounded from above by the following expression.
2d +d +1≤j≤n(3d +4dj +d)
= 3d + 4dn + 4d(1 + 2… + n)
≤3d+4dn+4dn2 ≤3dn2+4dn2+4dn2 =11dn2, for constant c = 11d > 0 and for each n > n0 = 1. Thus, the running time of the algorithm is O(n2).