# Recent questions tagged heap

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)$
1 vote
2
The number of elements that can be sorted in time using heap sort ?
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]$
1 vote
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})$
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$.
6
$6.2-3$ What is the effect of calling MAX-HEAPIFY(A,i) when the element A[i] is larger that its children?
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\}$
8
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)$
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 _________.
1 vote
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)$
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]
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))?
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}}$
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$
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$
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)$
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)$
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)$
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)$
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\}$
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$
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?
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$
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$
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.
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$
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\}$
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)$
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)$