Register

Recent questions tagged binary-heap

0 votes
0 answers
92
Cormen Edition 3 Exercise 6.3 Question 3 (Page No. 159)
Show that there are at most $\lceil n/2^{h+1}\rceil$ nodes of height $h$ in any $n-$element heap.
Show that there are at most $\lceil n/2^{h+1}\rceil$ nodes of height $h$ in any $n-$element heap.
User Avatar
0 votes
0 answers
93
Cormen Edition 3 Exercise 6.3 Question 2 (Page No. 159)
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$?
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...
User Avatar
0 votes
0 answers
94
Cormen Edition 3 Exercise 6.3 Question 1 (Page No. 159)
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 $
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...
User Avatar
0 votes
0 answers
98
Cormen Edition 3 Exercise 6.2 Question 3 (Page No. 156)
What is the effect of calling MAX-HEAPIFY$(A, i)$ when the element $A[i]$ is larger than its children?
What is the effect of calling MAX-HEAPIFY$(A, i)$ when the element $A[i]$ is larger than its children?
User Avatar
0 votes
1 answer
101
Algorithm-Self Doubt
How in a heap there are at most $\lceil \frac{n}{2^{h+1}} \rceil$ nodes of height h.
How in a heap there are at most $\lceil \frac{n}{2^{h+1}} \rceil$ nodes of height h.
User Avatar
0 votes
1 answer
103
ISI 2018 PCB C5
Consider a max-heap of n distinct integers, n ≥ 4, stored in an array A[1 . . . n]. The second minimum of A is the integer that is less than all integers in A except the minimum of A. Find all possible array indices of A in which the second minimum can occur. Justify your answer.
Consider a max-heap of n distinct integers, n ≥ 4, stored in an array A[1 . . . n]. The second minimum of A is the integer that is less than all integers in A except th...
User Avatar
3 votes
4 answers
104
IIIT PGEE 2019
What is the time complexity to delete an arbitrary node from binary heap? O(n) O(log n) O(1) O(n log n)
What is the time complexity to delete an arbitrary node from binary heap?O(n)O(log n)O(1)O(n log n)
User Avatar
1 votes
0 answers
105
Cormen Edition 3 Exercise 6.1 Question 7 (Page No. 154)
Show that, with the array representation for storing an $n$-element heap, the leaves are the nodes indexed by $\lfloor n/2\rfloor +1$,$\lfloor n/2\rfloor +2,…,n$
Show that, with the array representation for storing an $n$-element heap, the leaves are the nodes indexed by $\lfloor n/2\rfloor +1$,$\lfloor n/2\rfloor +2,…,n$
User Avatar
0 votes
2 answers
106
Cormen Edition 3 Exercise 6.1 Question 6 (Page No. 154)
Is the array with values $23,17,14; 6,13,10,1,5,7,12$ a max-heap ?
Is the array with values $23,17,14; 6,13,10,1,5,7,12$ a max-heap ?
User Avatar
3 votes
4 answers
108
Cormen Edition 3 Exercise 6.1 Question 4 (Page No. 154)
Where in a max-heap might the smallest element reside, assuming that all elements are distinct ?
Where in a max-heap might the smallest element reside, assuming that all elements are distinct ?
User Avatar
0 votes
0 answers
109
Cormen Edition 3 Exercise 6.1 Question 3 (Page No. 153)
Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in that subtree.
Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in that subtree.
User Avatar
0 votes
1 answer
111
Cormen Edition 3 Exercise 6.1 Question 1 (Page No. 153)
What are the minimum and maximum numbers of elements in a heap of height $h$?
What are the minimum and maximum numbers of elements in a heap of height $h$?
User Avatar
2 votes
1 answer
114
Finding the minimum element in a Heap
I was going through the heap concept and one question came into my mind what will be the best case time complexity of finding the minimum element in a max heap? Thank you:)
I was going through the heap concept and one question came into my mind what will be the best case time complexity of finding the minimum element in a max heap?Thank you:...
User Avatar
2 votes
0 answers
115
Madeeasy Max Heap 2019
Please explain the logic behind this shortcut and when to be used?
Please explain the logic behind this shortcut and when to be used?
User Avatar
0 votes
1 answer
116
UPPCL AE 2018:73
Consider the following array of elements $<70, 23, 60, 19, 13, 16, 1, 4, 8, 12, 7, 10, 85>$ The minimum number of interchanges needed to convert into a max-heap is $4$ $1$ $3$ $2$
Consider the following array of elements$<70, 23, 60, 19, 13, 16, 1, 4, 8, 12, 7, 10, 85>$The minimum number of interchanges needed to convert into a max-heap is $4$$1$$3...
User Avatar
0 votes
1 answer
117
UPPCL AE 2018:15
Match all items in $\text{Group 1}$ with the $\textbf{best}$ match from the options given in $\text{Group 2}.$ ... $\text{P-4, Q-3, R-2, S-1}$ $\text{P-3, Q-4, R-1, S-2}$
Match all items in $\text{Group 1}$ with the $\textbf{best}$ match from the options given in $\text{Group 2}.$$$\begin{array}{|l|l|} \hline \qquad \quad \textbf{Group 1} ...
User Avatar
Page: