Consider the following functions that implement the dequeue operation for a prio

Question

Consider the following functions that implement the dequeue operation for a priority queue that is implemented with a heap.

int[] pQueue;

int length;

int dequeue() {

int node = 1;

int value = pQueue[--length];

int maxValue = pQueue[node];

int location = sift(node * 2, value);

pQueue[location] = value; return maxValue;

}

int sift(int node, int value) {

if (node <= length) {

if (node < length && pQueue[node] < pQueue[node + 1])

node++;

if (value < pQueue[node]) {

pQueue[node / 2] = pQueue[node];

return sift(node * 2, value); } }

return node / 2;

}

1. Write the recurrence equation and initial conditions that expresses the execution time cost for the sift function in the above algorithm. Draw the recursion tree assuming that n = 8. Assume that n represents the number of nodes in the subtree at each step of the sifting operation.

2. Determine the critical exponent for the recurrence equation in problem 1. Apply the Little Master Theorem to solve that equation specifically stating which part of the theorem is applied to arrive at the solution.

Explanation / Answer

Each line before sift() method is called 1 time only . All instructions inside of sift() require constant time except the recursion call:

return sift(node * 2, value);

in the dequeue() method. it will call itself until node exceeds n–1 (node <= length, recalling that length decremented by 1). Bear in mind node doubles each time it recursively calls. Therefore, node doubles a number of times until it exceeds n thus it calls lg(n) times. That represents the worst case where value is the least element in pQueue’s heap subtrees. Since the recursion calls constant (1) instructions O(lg(n)) times, you should really not concern yourself with the constants in the recursion equation because all of it sums together under (1):

T(n) = O(lg(n)) + (1)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.