Recent questions tagged cormen

Argue the correctness of HEAP-INCREASE-KEY using the following loop invariant:At the start of each iteration of the while loop of lines $4–6$, the subarray $A[1..A.heapsi...

Why do we bother setting the key of the inserted node to $-\infty$ in line $2$ of MAX-HEAP-INSERT when the next thing we do is increase its key to the desired value?

Write pseudo code for the procedures HEAP-MINIMUM, HEAP-EXTRACT-MIN, HEAP-DECREASE-KEY, and MIN-HEAP-INSERT that implement a min-priority queue with a min-heap.

HEAP-INCREASE-KEY(A,i,key) 1 if key < A[i] 2 error “new key is smaller than current key” 3 A[i] = key 4 while i 1 and A[parent(i)] < A[i] 5 exchange A[i] with A[parent(i...

HEAP-EXTRACT-MAX(A) 1 if A.heap-size < 1 2 error “heap underflow” 3 max=A 4 A =A[A.heapsize] 5 A.heapsize=A.heapsize-1 6 MAX-HEAPIFY(A,1) 7 return max Illustrate th...

Show that when all elements are distinct, the best-case running time of HEAPSORT is $\Omega(n\lg\ n)$.

Show that the worst-case running time of HEAPSORT is $\Omega(n\lg\ n)$.

What is the running time of HEAPSORT on an array $A$ of length $n$ that is already sorted in increasing order? What about decreasing order?

Argue the correctness of HEAPSORT using the following loop invariant:At the start of each iteration of the for loop of lines $2–5$,the subarray $A[1..i]$ is a max-heap co...

HEAPSORT(A) 1 BUILD-MAX-HEAP(A) 2 for i = A.length down to 2 3 exchange A with A[i] 4 A.heapsize=A.heapsize – 1 5 MAX-HEAPIFY(A,1)illustrate the operation of HEAPSORT on...

Show that there are at most $\lceil n/2^{h+1}\rceil$ nodes of height $h$ in any $n-$element heap.

Why do we want the loop index $i$ in line $2$ of BUILD-MAX-HEAP to decrease from $\lfloor A.length/2 \rfloor$ to 1 rather than increase from 1 to $\lfloor A.length/2 \rfl...

BUILD-MAX-HEAP(A) 1 A.heapsize=A.length 2 for i=A.length/2 downto 1 3 MAX-HEAPIFY(A,i)Using Figure $6.3$ as a model, illustrate the operation of BUILD-MAX-HEAP on the arr...

Show that the worst-case running time of MAX-HEAPIFY on a heap of size $n$ is $\Omega(lg\ n)$.(Hint: For a heap with $n$ nodes, give node values that cause MAXHEAPIFY to ...

The code for MAX-HEAPIFY is quite efficient in terms of constant factors, except possibly for the recursive call in line 10, which might cause some compilers to produce i...

What is the effect of calling MAX-HEAPIFY$(A,i)$ for $i A.heapsize/2$.

What is the effect of calling MAX-HEAPIFY$(A, i)$ when the element $A[i]$ is larger than its children?

Starting with the procedure MAX-HEAPIFY, write pseudocode for the procedure MIN-HEAPIFY$(A, i )$, which performs the corresponding manipulation on a minheap. How does the...

MAX-HEAPIFY(A,i) 1 l=Left(i) 2 r=Right(i) 3 if l <= A.heapsize and A[l] A[i] 4 largest=l 5 else largest = i 6 if r <= A.heapsize and A[r] A[largest] 7 largest=r...

Give an algorithm that determines the number of inversions in any permutation on $n$ elements in $\Theta (n\ lg\ n)$ worst-case time. (Hint: Modify merge sort.)

What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.

Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence $A$ is sorted, we can check the midpoint of the sequence against $v$ and elimin...

Rewrite the MERGE procedure so that it does not use sentinels, instead of stopping once either array $L$ or $R$ has had all its elements copied back to $A$ and then copyi...