# Recent questions tagged heap 2 votes
3 answers
1
​​​​​Let $H$ be a binary min-heap consisting of $n$ elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in $H$? $\Theta (1)$ $\Theta (\log n)$ $\Theta (n)$ $\Theta (n \log n)$
0 votes
1 answer
2
Consider the process of inserting an element into a $Max\ Heap$, where the $Max\ Heap$ is represented by an $array$. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of $comparisons$ performed is $\Theta(\log _{2}n)$ $\Theta(n\log _{2} \log_2 n)$ $\Theta (n)$ $\Theta(n\log _{2}n)$
0 votes
1 answer
3
A priority queue is implemented as a Max-Heap. Initially, it has $5$ elements. The level-order traversal of the heap is: $10,8,5,3,2$. Two new elements $1$ and $7$ are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is $10,8,7,3,2,1,5$ $10,8,7,2,3,1,5$ $10,8,7,1,2,3,5$ $10,8,7,5,3,2,1$
0 votes
2 answers
4
Consider a complete binary tree where the left and the right sub trees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is: $\Omega(\log n)$ $\Omega(n\log n)$ $\Omega(n)$ $\Omega(n^2)$
0 votes
6 answers
5
Which of the following is a valid heap? $a$ $b$ $c$ $d$
0 votes
1 answer
6
A 3 way (ternary) min heap is a 3 way ( ternary - each node as atmost three children nodes, left, mid, right ) complete tree with min heap property ( value of the parent is less than the value of the children ) satisfied at every node. Given a ternary ... function. (c) In Heapsort, binary heap is preferred over ternary heap. State if this statement is true or false, you must justify your answer.
0 votes
0 answers
7
Give an $O(n\lg\ k)$- time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total number of elements in all the input lists. (Hint: Use a minheap for $k$-way merging.)
0 votes
1 answer
8
The operation HEAP-DELETE$(A, i)$ deletes the item in node $i$ from heap $A$. Give an implementation of HEAP-DELETE that runs in $O(lg\ n)$ time for an $n-$element max-heap.
0 votes
0 answers
9
Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue.
0 votes
0 answers
10
Each exchange operation on line $5$ of HEAP-INCREASE-KEY typically requires three assignments. Show how to use the idea of the inner loop of INSERTION-SORT to reduce the three assignments down to just one assignment.
0 votes
0 answers
11
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.heapsize]$ satisfies the max-heap property, except that there may be one violation$::$ $A[i]$ may be ... $A[a..heapsize]$ satisfies the max-heap property at the time HEAP-INCREASE-KEY is called.
0 votes
0 answers
12
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?
0 votes
0 answers
13
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.
0 votes
0 answers
14
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)] 6 i=parent(i) MAX-HEAP-INSERT(A,key) 1 A.heapsize = A.heapsize + 1 2 A[A.heapsize] ... -KEY(A,A.heapsize,key) Illustrate the operation of MAX-HEAP-INSERT$(A,10)$ on the heap $A=\langle 15,13,9,5,12,8,7,4,0,6,2,1 \rangle$.
0 votes
0 answers
15
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 the operation of HEAP-EXTRACT-MAX on the heap $A=\langle 15,13,9,5,12,8,7,4,0,6,2,1 \rangle$.
0 votes
0 answers
16
Show that when all elements are distinct, the best-case running time of HEAPSORT is $\Omega(n\lg\ n)$.
0 votes
0 answers
17
Show that the worst-case running time of HEAPSORT is $\Omega(n\lg\ n)$.
0 votes
0 answers
18
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?
0 votes
0 answers
19
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 containing the $i$ smallest elements of $A[1..n]$, and the subarray $A[i+1..n]$ contains the $n- i$ largest elements of $A[1..n]$, sorted.
0 votes
0 answers
20
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 the array $A=\langle 5,13,2,25,7,17,20,8,4 \rangle$
0 votes
0 answers
21
Show that there are at most $\lceil n/2^{h+1}\rceil$ nodes of height $h$ in any $n-$element heap.
0 votes
0 answers
22
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 \rfloor$?
0 votes
0 answers
23
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 array $A=\langle 5,3,17,10,84,19,6,22,9 \rangle$
0 votes
0 answers
24
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 be called recursively at every node on a simple path from the root down to a leaf).
0 votes
0 answers
25
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 inefficient code. Write an efficient MAX-HEAPIFY that uses an iterative control construct (a loop) instead of recursion.
0 votes
0 answers
26
What is the effect of calling MAX-HEAPIFY$(A,i)$ for $i > A.heapsize/2$.
0 votes
0 answers
27
What is the effect of calling MAX-HEAPIFY$(A, i)$ when the element $A[i]$ is larger than its children?