# Recent questions tagged heap

1
Is the array with values $23,17,14; 6,13,10,1,5,7,12$ a max-heap ?
2
Is an array that is in sorted order a min-heap ?
1 vote
3
Where in a max-heap might the smallest element reside, assuming that all elements are distinct ?
4
Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in that subtree.
5
Show that an $n$-element heap has height $\lfloor lg\ n \rfloor$.
6
What are the minimum and maximum numbers of elements in a heap of height $h$?
7
Consider the following statements: The smallest element in a max-heap is always at a leaf node The second largest element in a max-heap is always a child of a root node A max-heap can be constructed from a binary search tree in $\theta(n)$ time A binary search tree can be constructed ... time Which of te above statements are TRUE? I, II and III I, II and IV I, III and IV II, III and IV
1 vote
8
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:)
1 vote
9
Please explain the logic behind this shortcut and when to be used?
10
what is the time complexity of various problems such as: 1) Creating the heap 2) Getting maximum element in the max heap 3) Getting minimum element in the max heap 4) Getting maximum element in min heap 5) Getting minimum element in min heap 6) Heapify the element 7) ... ) Deletion of an element in the max heap 10) Insertion of an element in the max heap 11) Insertion of an element in min heap
11
Consider the following modified Heapify and Build_heap procedure. void Heapify(int* A, int i, int n) { int left=2*i+1; int right=2*i+2; int mid=i; if (left<=n && right <=n) { if ((A[left] > A[right] && A[left]< A[i]) || A[left]<A[right] && A[left] >A[i]) mid=left; else if((A[left<A[right] && A[right]<A[i]) ... $6 \: 8 \: 1 \: 9 \: 4$ $9 \: 6 \: 1 \: 8 \: 4$ $6 \: 9 \: 1 \: 8 \: 4$
1 vote
12
What is the time complexity of 'deleting any random node from a max or min heap'?
13
For the given nodes: $89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100$ minimum ______ number of interchanges are required to convert it into a max-heap. $3$ $4$ $5$ $6$
14
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)?
15
Consider there are n/logn min heap trees each of size logn. What will be the time complexity to find the smallest element and greatest element in these min heap trees respectively? A) O(n/logn), O(n) B) O(n), O(n/logn) C) O(n), O(n) D) O(logn), O(logn)
1 vote
16
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?
17
The minimum number of comparisons required to find the 65th smallest element in a minheap is equal to
18
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.
19
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.
1 vote
20
Does Heap Allocation support both recursion and dynamic memory allocation? Because,a stack can be implemented using dynamic memory allocation.Please correct me. Test Series answer shows only dynamic memory allocation
21
$(1)$ In a binary heap with $'n'$ elements with the smallest element at the root, the $7th$ smallest element can be found in time? $A)\theta(nlogn)$ $B)\theta(n)$ $C)\theta(logn)$ $D)\theta(1)$ $(2)$ In binary max heap containing $'n'$ numbers, the smallest element can be ... ) into this heap. The total time required for this is? $A)\theta(logn)$ $B)\theta(n)$ $A)\theta(nlogn)$ $A)\theta(n^{2})$
1 vote
22
The minimum no. of comparison required to find 65 th smallest element in min heap is
23
https://gateoverflow.in/?qa=blob&qa_blobid=17275535249024428371
24
What is the number of comparisons required to extract 45th element of the min heap?
25
What is Binomial tree please explain in easy words. Construct the Binomial heap for the following sequence of numbers 7,2,4,17,1,11,6,8,15,10,20. Also apply the operation of extracting the minimum key in the resulting binomial Heap.
26
Sort The Following Sequence of input using Heap sort. { 10 , 2 , 1 , 5, 3 ,8 ,11,24 ,7 } Please show the output at every pass because i am getting confused.
27
How traversal in a heap takes place? Consider a min heap , I think we cannot traverse it like a binary tree ......For Example if we have to print all elements of heap Do we need to perform delete operation on root O(1) time then perform Heapify O(lgn) and again perform delete and so on which overall takes O(N) time ? Whether same is for search as well Plz explain...
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}$
a)Deletion of smallest element in heap b)Insertion of an element in a heap will take $O(n)$ or $O(logn)$ time?