search
Log In

Recent questions tagged binary-heap

0 votes
2 answers
1
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$
asked Mar 30 in DS Lakshman Patel RJIT 51 views
0 votes
1 answer
2
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.
asked May 2, 2019 in Algorithms N 107 views
1 vote
2 answers
3
What is the time complexity to delete an arbitrary node from binary heap? O(n) O(log n) O(1) O(n log n)
asked Apr 29, 2019 in Programming manikgupta123 472 views
1 vote
1 answer
4
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:)
asked Jan 15, 2019 in DS Nandkishor3939 560 views
1 vote
0 answers
5
1 vote
1 answer
6
What is the time complexity of 'deleting any random node from a max or min heap'?
asked Dec 21, 2018 in DS Avijit Shaw 835 views
0 votes
0 answers
7
https://gateoverflow.in/459/gate2008-47 here if we insert all elements together and then call heapify function then it’ll take O(logn) time. why answer is O(n)?
asked Dec 4, 2018 in Algorithms aditi19 73 views
1 vote
1 answer
8
What is the time complexity to find the Kth largest element in a Min-Heap? Or equivalently, What is the time complexity to find Kth smallest element in Max-Heap?
asked Dec 1, 2018 in Algorithms gmrishikumar 474 views
1 vote
0 answers
9
Consider a binary min heap given below containing integer in [1, 15]. The maximum number of node movement on 5 successive removal of element are ________.
asked Nov 20, 2018 in DS codingo1234 291 views
0 votes
0 answers
10
This question is in CLRS,if we have a max heap it is always in sorted order(descending) order.And by extension if we have min heap the array is sorted in ascending order.Is this true? I have a counter example for 100,50,20,1,3,10,5,this satisfied max- ... it as an array is it an heapified representation or not? If we heapify after deletion and store max deleted element then we get sorted array.
asked Nov 15, 2018 in DS sripo 549 views
0 votes
1 answer
11
For a heap containing n elements,smallest element can be found in n/2 operations.I always get confused and think as logn operations.Please help me differentiating between these two times.
asked Nov 8, 2018 in DS sripo 147 views
0 votes
0 answers
12
what i did {$2^{h+1}-1=100$} so i found h=6 so max swaps needed would be 6 please check it or tell me if i iam wrong
asked Oct 23, 2018 in Programming Prince Sindhiya 90 views
0 votes
0 answers
13
What is the number of comparisons required to extract 45th element of the min heap?
asked Sep 10, 2018 in Algorithms bts1jimin 610 views
0 votes
1 answer
14
asked Aug 29, 2018 in Programming Shubham Aggarwal 67 views
0 votes
0 answers
15
Consider a binary tree, where left and right subtreealready heapified. But we havenot done heapificationfor root yet. Then what is time complexity to convert it in a full heap tree? $A)O(\log n)$ or $o(n)$ $B)\Omega (\log n)$ or $\omega(n)$ $C)\Theta (\log n)$ or $\theta (n)$ $D)\text{None of these}$
asked Aug 18, 2018 in DS srestha 505 views
0 votes
1 answer
16
The number of distinct min heap are possible with keys 1, 2, 3, 4, 5 are ________. I know, there are variance of this question for Max heap and even for Min heap, the answer won't change, but I just wanna know if my technique is right or not. ====================== ... and right child can get any value. -> Lastly the right sub tree => 1C1 = 1 Totally - 1*4C3*1*2*1 = 8. Is this approach correct?
asked Jun 24, 2018 in DS iarnav 183 views
0 votes
0 answers
17
The number of possible min-heaps containing each value from {1,1,1,1,1,1,1} exactly once is _______ This is a variance of Gate 2018 question and how will we deal if all values are same?
asked Jun 24, 2018 in DS iarnav 84 views
3 votes
1 answer
18
A min heap having 1024 distinct elements with keys ranging from 0 to 1023 is stored in array of 1024 indices. The maximum difference between element 512 present at maximum level and minimum level is ________. [Assume root is ... are taking maximum level 11 and minimum level 2 __________________________________________________________________________ why minimum level 2, and why it is not 1?
asked Jun 24, 2018 in Programming srestha 803 views
0 votes
1 answer
19
I've read and been told that Heapsort can only be applied on Max heap, but this article for G4G states otherwise - https://www.geeksforgeeks.org/heap-sort-for-decreasing-order-using-min-heap/ So, is it true that HS can be applied also on Min heap?
asked Jun 20, 2018 in Algorithms iarnav 213 views
0 votes
1 answer
20
Let's say we're given with a MAX Heap and we want to delete any of the leaf node, then how much time will it take to delete any of the leaf node and maintain the max heap property? My main doubt is - will it O(n) time to reach to leaf nodes?
asked Jun 19, 2018 in DS iarnav 159 views
1 vote
0 answers
21
How many max-heaps can be formed with the following elements? $\{1,1,1,2,2,2,3,3,3,4,4,4\}$
asked Jun 4, 2018 in DS Balaji Jegan 497 views
1 vote
1 answer
22
Question Source - https://gateoverflow.in/1374/gate2005-38 Let G(V,E)be an undirected graph with positive edge weights. Dijkstra's single source shortest path algorithm can be implemented using the binary heap data structure with time complexity: 1. O(|V|2) 2. O(|E|+|V|log|V|) 3. O(|V|log|V|) ... |V| = |E|, but as I > said the correct answer is O((|E|+|V|)log|V|). So, where am I going > wrong?
asked May 22, 2018 in Algorithms iarnav 531 views
0 votes
0 answers
23
A min heap having $1024$ distinct elements with keys ranging from $0$ to $1023$ is stored in array of $1024$ indices. The maximum difference between $(n/2)^{th}$ element present at maximum level and minimum level is ________. [Assume root is present at $level-1$] ? Please Tell me the Approach
asked May 20, 2018 in Algorithms Na462 103 views
0 votes
1 answer
24
How much time will it take for deleting $i^{th}$ and a number $n(random)$ node from a heap ?
asked Apr 28, 2018 in Algorithms Akash Kumar Roy 247 views
4 votes
2 answers
25
Given a binary-max heap. The elements are stored in an arrays as $25, 14, 16, 13, 10, 8, 12$. What is the content of the array after two delete operations? $14,13,8,12,10$ $14,12,13,10,8$ $14,13,12,8,10$ $14,13,12,10,8$
asked Apr 22, 2018 in Others Arjun 2.4k views
0 votes
1 answer
26
what is Potential function in Fibonacci heap (i dont remember the question ) plz explain with example
asked Mar 30, 2018 in Algorithms akshat sharma 120 views
0 votes
0 answers
27
My question is in Question like find 5th Smallest element in a heap: It requires O(logn) time if we do only Delete operation 5 Times.But what if the array contains no 5th smallest element say our array contain [1,1,1,1,1,1,1,1,1,1] now in this case we need to do extract min operation n number of times which would give nlogn time? Plz Clear my doubt https://gateoverflow.in/1110/gate2003-23
asked Feb 17, 2018 in Algorithms Na462 241 views
3 votes
2 answers
28
The number of distinct max heap are possible with keys 1, 2, 3, 4, 5 are ________.
asked Jan 20, 2018 in DS MIRIYALA JEEVAN KUMA 308 views
4 votes
1 answer
29
1 vote
3 answers
30
The number of ways in which the numbers 1, 2, 3, 4, 5 can be inserted into binary heap. Such that resulted binary heap is max heap ________.
asked Nov 7, 2017 in DS shivangi5 803 views
...