GATE CS Binary Heaps questions

The height of any rooted tree is defined as the maximum number of edges in the path from the root node to any leaf node. Suppose a Min-Heap $\text{T}$ stores $32$ keys. The height of $\text{T}$ is ___________. (Answer in integer)

Consider a binary min-heap containing $105$ distinct elements. Let $k$ be the index (in the underlying array) of the maximum element stored in the heap. The number of possible values of $k$ is

Which one of the following sequences when stored in an array at locations $A[1], \ldots, A[10]$ forms a max-heap?

Let $A$ be a priority queue for maintaining a set of elements. Suppose $A$ is implemented using a max-heap data structure. The operation $\text{EXTRACT-MAX} (A)$ extracts and deletes the maximum element from $A$. The operation $\operatorname{INSERT}(A, key )$ inserts a new element $key$ in $A$. The properties of a max-heap are preserved at the …

​​​​​Let $H$ be a binary min-heap consisting of $n$ elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in $H$?

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 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 from a max-heap in $\Theta(n)$ time Which of the above statements are …

The number of possible min-heaps containing each value from $\{1,2,3,4,5,6,7\}$ exactly once is _______

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 ), then what is the time complexity to …

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 _________.

Consider a max heap, represented by the array: $40, 30, 20, 10, 15, 16, 17, 8, 4$. …

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

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

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:

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?

Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?

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\}$

Consider the process of inserting an element into a $\text{Max Heap}$, where the $\text{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:

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]$, nodes in the next level, from left to right, is stored from $a[1]$ to $a[3]$. The nodes …

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]$, nodes in the next level, from left to right, is stored from $a[1]$ to $a[3]$. The nodes …