search
Log In

Recent questions tagged heap

3 votes
2 answers
1
The number of nodes in height h in any n-element heap is $h$ $z^h$ ceil $\biggl(\frac{n}{z^h} \biggr)$ ceil $\biggl(\frac{n}{z^{h+1}} \biggr)$
asked Aug 1, 2016 in DS jothee 734 views
1 vote
1 answer
2
The number of elements that can be sorted in time using heap sort ?
asked Jul 30, 2016 in Algorithms reena_kandari 517 views
0 votes
1 answer
3
In any n-element heap, the number of nodes of height h is, less than equal to $\biggl[ \frac{n}{2^h} \biggr]$ greater than $\biggl[ \frac{n}{2^h} \biggl]$ greater than $\biggl[ \frac{n}{2^h+1} \biggr]$ less than equal to $\biggl [ \frac{n}{2^h+1} \biggr]$
asked Jul 16, 2016 in DS jothee 441 views
1 vote
1 answer
4
Suppose there are $\log_n$ sorted lists of $n \log_n$ element each. The time complexity of producing a sorted list of all these elements is (use heap data structure) $O (n \log \log_n)$ $\theta (n \log_n)$ $\Omega (n \log_n)$ $\Omega (n^{3/2})$
asked Jul 13, 2016 in Algorithms jothee 625 views
11 votes
1 answer
5
Let $H_1$ and $H_2$ be two complete binary trees that are heaps as well. Assume $H_1$ and $H_2$ are max-heaps, each of size $n$. Design and analyze an efficient algorithm to merge $H_1$ and $H_2$ to a new max-heap $H$ of size $2n$.
asked May 31, 2016 in DS jothee 604 views
0 votes
1 answer
6
$6.2-3$ What is the effect of calling MAX-HEAPIFY(A,i) when the element A[i] is larger that its children?
asked May 17, 2016 in Algorithms Shyam Singh 1 279 views
17 votes
3 answers
7
Consider a binary max-heap implemented using an array. What is the content of the array after two delete operations on $\left\{25,14,16,13,10,8,12\right\}$ $\left\{14,13,12,10, 8\right\}$ $\left\{14,12,13,8,10\right\}$ $\left\{14,13,8,12,10\right\}$ $\left\{14,13,12,8,10\right\}$
asked Apr 23, 2016 in DS jothee 2.1k views
34 votes
3 answers
9
An operator $delete(i)$ for a binary heap data structure is to be designed to delete the item in the $i$-th node. Assume that the heap is implemented in an array and $i$ refers to the $i$-th index of the array. If the heap tree has depth $d$ (number of edges on the path from the root to the farthest leaf ), ... ? $O(1)$ $O(d)$ but not $O(1)$ $O(2^d)$ but not $O(d)$ $O(d \ 2^d)$ but not $O(2^d)$
asked Feb 12, 2016 in DS Sandeep Singh 6k views
52 votes
5 answers
10
A complete binary min-heap is made by including each integer in $[1, 1023]$ exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth $0$. The maximum depth at which integer $9$ can appear is _________.
asked Feb 12, 2016 in DS Akash Kanase 9.2k views
1 vote
1 answer
11
What is the Best Case run time of Heap Sort ? A. $O(1)$ B. $O(n)$ C. $O(n \log n)$ D. $O(\log n)$
asked Jan 20, 2016 in Algorithms Himanshu1 565 views
0 votes
1 answer
12
Consider the following "Max Heapify" algorithm. Array has atleast n and 1<=i<=n. After applying the Max-heapify rooted at A[i], the result will be subtree of A[1,....n] rooted at A[i] is max heap. [Assume that except root A[i], all its children satisfied heap property] Max-heapify(int A[], int n, int i) { int p ... A[2p+1]>A[2p] c) 2p<=n, (2p+1)>=n, A[2p+1]<A[2p] d) p<=n, (2p+1)<=n, A[2p+1]<A[2p]
asked Dec 30, 2015 in Algorithms piyushkr 567 views
4 votes
1 answer
13
# heaps Min or Max_ consider any! Give recurrence relation / math expression For What is the number of min heaps possible with $n$ distinct elements? What is the number of min heaps possible with $n$ elements on which $k$ elements are repeated $t$ times where $t=0$ to infinite (rather considering infinite consider some max value (countable))?
asked Nov 24, 2015 in DS Ravi Raaja 1.9k views
29 votes
4 answers
14
Consider the following tree with $13$ nodes. Suppose the nodes of the tree are randomly assigned distinct labels from $\left\{1, 2,\ldots,13\right\}$, each permutation being equally likely. What is the probability that the labels form a min-heap (i.e., every node receives the minimum label in its subtree)? ... $\frac{2}{13}$ $\frac{1}{2^{13}}$
asked Nov 20, 2015 in DS makhdoom ghaya 1.9k views
21 votes
4 answers
15
Consider the following array of elements. $\langle 89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100 \rangle$ The minimum number of interchanges needed to convert it into a max-heap is $4$ $5$ $2$ $3$
asked Feb 14, 2015 in DS jothee 2.4k views
21 votes
2 answers
16
Consider a max heap, represented by the array: $40, 30, 20, 10, 15, 16, 17, 8, 4$ ... $40, 30, 20, 10, 35, 16, 17, 8, 4, 15$ $40, 35, 20, 10, 15, 16, 17, 8, 4, 30$
asked Feb 13, 2015 in DS makhdoom ghaya 2.1k views
38 votes
4 answers
17
Consider a complete binary tree where the left and right subtrees 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)$ $\Omega(n \log n)$ $\Omega(n^2)$
asked Feb 12, 2015 in DS jothee 5.4k views
9 votes
6 answers
18
What is the complexity of finding $50^{th}$ smallest element in an already constructed binary min-heap? $\Theta(1)$ $\Theta (\log n)$ $\Theta (n)$ $\Theta (n \log n)$
asked Dec 28, 2014 in Algorithms Vikrant Singh 1.2k views
29 votes
4 answers
19
An array of integers of size $n$ can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node $\left \lfloor (n - 1) /2 \right \rfloor$, and doing this adjustment up to the root node (root node is at index $0$) in the ... time required to construct a heap in this manner is $O(\log n)$ $O(n)$ $O (n \log \log n)$ $O(n \log n)$
asked Nov 2, 2014 in DS Ishrat Jahan 3.6k views
23 votes
3 answers
20
An array $X$ of $n$ distinct integers is interpreted as a complete binary tree. The index of the first element of the array is $0$. If only the root node does not satisfy the heap property, the algorithm to convert the complete binary tree into a heap has the best asymptotic time complexity of $O (n)$ $O (\log n)$ $O (n \log n)$ $O (n \log \log n)$
asked Nov 1, 2014 in DS Ishrat Jahan 2.7k views
15 votes
1 answer
21
Which of the following sequences of array elements forms a heap? $\{23, 17, 14, 6, 13, 10, 1, 12, 7, 5\}$ $\{23, 17, 14, 6, 13, 10, 1, 5, 7, 12\}$ $\{23, 17, 14, 7, 13, 10, 1, 5, 6, 12\}$ $\{23, 17, 14, 7, 13, 10, 1, 12, 5, 7\}$
asked Nov 1, 2014 in DS Ishrat Jahan 1.4k views
19 votes
2 answers
22
The minimum number of interchanges needed to convert the array into a max-heap is $89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70$ $0$ $1$ $2$ $3$
asked Oct 9, 2014 in DS Kathleen 4.9k views
17 votes
2 answers
23
A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?
asked Sep 29, 2014 in DS jothee 2.3k views
14 votes
3 answers
24
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 Sep 28, 2014 in DS jothee 1.7k views
18 votes
2 answers
25
Statement for Linked Answer Questions 76 & 77: A $3$-ary max heap is like a binary max heap, but instead of $2$ children, nodes have $3$ children. A $3$-ary heap can be represented by an array as follows: The root is stored in the first location, $a[0]$ ... $1, 3, 5, 6, 8, 9$ $9, 6, 3, 1, 8, 5$ $9, 3, 6, 8, 5, 1$ $9, 5, 6, 8, 3, 1$
asked Sep 26, 2014 in DS Rucha Shelke 1.9k views
15 votes
3 answers
26
In binary tree, a full node is defined to be a node with $2$ children. Use induction on the height of the binary tree to prove that the number of full nodes plus one is equal to the number of leaves. Draw the min-heap that results from insertion of the following elements in order into an initially empty min-heap: $7, 6, 5, 4, 3, 2, 1$. Show the result after the deletion of the root of this heap.
asked Sep 24, 2014 in DS Kathleen 1.5k views
13 votes
2 answers
27
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, 5, 3, 2, 1$ $10, 8, 7, 2, 3, 1, 5$ $10, 8, 7, 1, 2, 3, 5$ $10, 8, 7, 3, 2, 1, 5$
asked Sep 22, 2014 in DS Kathleen 2.8k views
15 votes
3 answers
28
Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap? $\left\{25,12,16,13,10,8,14\right\}$ $\left\{25,14,13,16,10,8,12\right\}$ $\left\{25,14,16,13,10,8,12\right\}$ $\left\{25,14,12,13,10,8,16\right\}$
asked Sep 22, 2014 in DS Kathleen 2.3k views
43 votes
3 answers
29
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_2n)$ $\Theta(\log_2\log_2n)$ $\Theta(n)$ $\Theta(n\log_2n)$
asked Sep 22, 2014 in DS Kathleen 6.4k views
41 votes
6 answers
30
In a min-heap with $n$ elements with the smallest element at the root, the $7^{th}$ smallest element can be found in time $\Theta (n \log n)$ $\Theta (n)$ $\Theta(\log n)$ $\Theta(1)$
asked Sep 19, 2014 in DS Disha 11.7k views
...