Register

Recent questions tagged binary-heap

1 votes
2 answers
61
Gate Applied Practice Test
Question--> The time required to find the 99th smallest element from a min heap of n elements is (given that we have access to the array elements)
Question The time required to find the 99th smallest element from a min heap of n elements is (given that we have access to the array elements)
User Avatar
0 votes
2 answers
62
Gate-Applied-test
Which of the following arrays do not represent a min heap. A. 1, 2, 4, 8, 12, 6, 7, 10, 11 7, 10, 12, 11, 17, 19, 2 25, 27, 28, 30, 32, 34, 27 90, 95, 100, 110, 120, 130, 99
Which of the following arrays do not represent a min heap. A. 1, 2, 4, 8, 12, 6, 7, 10, 11 7, 10, 12, 11, 17, 19, 2 25, 27, 28, 30, 32, 34, 27 90, 95, 100, 11...
User Avatar
2 votes
1 answer
63
Applied Test Series
The time required to determine the minimum element from the max heap of size O(log(n)) is given by
The time required to determine the minimum element from the max heap of size O(log(n)) is given by
User Avatar
1 votes
2 answers
64
Self Doubt
How many min heap possible with 6 distinct node?
How many min heap possible with 6 distinct node?
User Avatar
3 votes
3 answers
66
UGC NET CSE | October 2020 | Part 2 | Question: 24
In a binary max heap containing $n$ numbers, the smallest element can be found in ______ $O(n)$ $O(\log _2 n)$ $O(1)$ $O(\log_2 \log_2 n)$
In a binary max heap containing $n$ numbers, the smallest element can be found in ______$O(n)$$O(\log _2 n)$$O(1)$$O(\log_2 \log_2 n)$
User Avatar
1 votes
1 answer
67
NIELIT 2016 MAR Scientist C - Section C: 49
We have a binary heap on $n$ elements and wish to insert $n$ more elements (not necessarily one after another) into this heap. Total time required for this is $\Theta (\log n)$ $\Theta (n)$ $\Theta (n \log n)$ $\Theta (n^{2})$
We have a binary heap on $n$ elements and wish to insert $n$ more elements (not necessarily one after another) into this heap. Total time required for this is$\Theta (\lo...
User Avatar
2 votes
2 answers
70
NIELIT 2017 DEC Scientist B - Section B: 31
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)$
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 he...
User Avatar
1 votes
7 answers
71
UGC NET CSE | January 2017 | Part 2 | Question: 23
Which of the following is a valid heap? $a$ $b$ $c$ $d$
Which of the following is a valid heap? $a$$b$$c$$d$
User Avatar
28 votes
6 answers
72
GATE CSE 2020 | Question: 47
Consider the array representation of a binary min-heap containing $1023$ elements. The minimum number of comparisons required to find the maximum in the heap is ___________.
Consider the array representation of a binary min-heap containing $1023$ elements. The minimum number of comparisons required to find the maximum in the heap is _________...
User Avatar
0 votes
0 answers
74
Cormen Edition 3 Exercise 6.5 Question 9 (Page No. 166)
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.)
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 minhea...
User Avatar
0 votes
1 answer
75
Cormen Edition 3 Exercise 6.5 Question 8 (Page No. 166)
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.
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-h...
User Avatar
0 votes
0 answers
76
Cormen Edition 3 Exercise 6.5 Question 7 (Page No. 166)
Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue.
Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue.
User Avatar
0 votes
0 answers
77
Cormen Edition 3 Exercise 6.5 Question 6 (Page No. 166)
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.
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 ...
User Avatar
0 votes
0 answers
79
Cormen Edition 3 Exercise 6.5 Question 4 (Page No. 165)
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?
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?
User Avatar
1 votes
0 answers
80
Cormen Edition 3 Exercise 6.5 Question 3 (Page No. 165)
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.
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.
User Avatar
0 votes
0 answers
83
Cormen Edition 3 Exercise 6.4 Question 5 (Page No. 161)
Show that when all elements are distinct, the best-case running time of HEAPSORT is $\Omega(n\lg\ n)$.
Show that when all elements are distinct, the best-case running time of HEAPSORT is $\Omega(n\lg\ n)$.
User Avatar
0 votes
0 answers
85
Cormen Edition 3 Exercise 6.4 Question 3 (Page No. 160)
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?
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?
User Avatar
Page: