Heap Practice Questions

1. For an unsorted doubly linked list (P), merging two lists can be done by simply connecting the tail of one list to the head of the other, which takes $\Theta(1)$ time.
2. For a min-heap implemented using an array (Q), merging two heaps of size $n$ can be done by combining the arrays and then building a new heap. Building a heap from an array of $2n$ elements takes $\Theta(n)$ time.
3. For a Binary Search Tree (R), merging two BSTs of size $n$ can be done by traversing one tree to get its elements, inserting them into the other tree. In the worst case, this can take $\Theta(n^2)$ if the resulting tree becomes skewed. Alternatively, one can collect all elements into a sorted array ($\Theta(n)$), and build a balanced BST ($\Theta(n)$). The solution states $\Theta(n)$ but implies a sorted list merge or traversal approach.
4. The worst-case time complexities are: P: $\Theta(1)$, Q: $\Theta(n)$, R: $\Theta(n)$.

To determine the height of a Min-Heap with 32 keys, we first recall that a heap is a complete binary tree. This means all levels are fully filled, except possibly the last level, which is filled from left to right.

The height $h$ of a complete binary tree with $N$ nodes satisfies the inequality:
$2^h \le N < 2^{h+1}$
Given $N = 32$ keys, we substitute this into the inequality:
$2^h \le 32 < 2^{h+1}$
We know that $2^5 = 32$.
Substituting this, we get:
$2^h \le 2^5 < 2^{h+1}$
From this, it implies that $h = 5$.
The height of the Min-Heap with 32 keys is 5.

[CORRECT_OPTION: 5]

Heapify refers to building a heap from an arbitrary array. For a max-heap, this means arranging the elements such that the parent node is always greater than or equal to its children. A common algorithm is Floyd's build-heap algorithm, which works bottom-up.

Given array: $[82, 101, 90, 11, 111, 75, 33, 131, 44, 93]$
This array represents a complete binary tree (CBT) where elements are stored level by level.
Let's visualize the initial CBT:
Level 0: 82
Level 1: 101, 90
Level 2: 11, 111, 75, 33
Level 3: 131, 44, 93 (remaining elements)

Heapify (build max-heap) starts from the last non-leaf node and moves upwards. The last non-leaf node is at index $\lfloor N/2 \rfloor - 1$. For N=10, last non-leaf is at index $\lfloor 10/2 \rfloor - 1 = 4$. This is element 111 (at index 4 in 0-indexed array).

However, the question asks for the first three elements of the heapified array. This implies the array structure after the heap property is established, meaning the largest element will be at the root, and its children will be the next largest.

Let's trace the heapify process by applying heapify (or max_heapify) on nodes from bottom-up:
Initial array: $A = [82, 101, 90, 11, 111, 75, 33, 131, 44, 93]$ (Indices 0 to 9)

1. Nodes at index 4 (111), 3 (11):
   Node at index 4 (111) has children at indices 9 (93) and potentially 10 (none).
   Node at index 3 (11) has children at indices 7 (131) and 8 (44).
   Max_heapify(A, 3) (element 11): Compare 11 with 131 and 44. Swap 11 with 131.
   $A = [82, 101, 90, \underline{131}, 111, 75, 33, \underline{11}, 44, 93]$
   Max_heapify(A, 4) (element 111): Compare 111 with 93. No swap.
   $A = [82, 101, 90, 131, 111, 75, 33, 11, 44, 93]$

2. Nodes at index 2 (90):
   Max_heapify(A, 2) (element 90): Compare 90 with 75 and 33. No swap.
   $A = [82, 101, 90, 131, 111, 75, 33, 11, 44, 93]$

3. Nodes at index 1 (101):
   Max_heapify(A, 1) (element 101): Compare 101 with 131 (left child) and 111 (right child). Swap 101 with 131.
   $A = [82, \underline{131}, 90, \underline{101}, 111, 75, 33, 11, 44, 93]$
   The swapped 101 is now at index 3. Its children are 11 and 44. Max_heapify(A, 3) (element 101): Compare 101 with 11 and 44. No swap.
   $A = [82, 131, 90, 101, 111, 75, 33, 11, 44, 93]$

4. Nodes at index 0 (82):
   Max_heapify(A, 0) (element 82): Compare 82 with 131 (left child) and 90 (right child). Swap 82 with 131.
   $A = [\underline{131}, \underline{82}, 90, 101, 111, 75, 33, 11, 44, 93]$
   The swapped 82 is now at index 1. Its children are 101 and 111. Max_heapify(A, 1) (element 82): Compare 82 with 101 and 111. Swap 82 with 111.
   $A = [131, \underline{111}, 90, 101, \underline{82}, 75, 33, 11, 44, 93]$
   The swapped 82 is now at index 4. Its child is 93. Max_heapify(A, 4) (element 82): Compare 82 with 93. Swap 82 with 93.
   $A = [131, 111, 90, 101, \underline{93}, 75, 33, 11, 44, \underline{82}]$

The final heapified array is $[131, 111, 90, 101, 93, 75, 33, 11, 44, 82]$.
The first three elements are $131, 111, 90$.

In a binary min-heap, the minimum element is always at the root (index 0).
The maximum element, however, can be any of the leaf nodes.
For a heap with $N$ elements, the leaf nodes are located at indices from $\lfloor N/2 \rfloor$ to $N-1$ (assuming 0-indexed array representation).
Given $N=105$ distinct elements.
The indices of the leaf nodes range from $\lfloor 105/2 \rfloor = 52$ to $105-1 = 104$.
So, the maximum element can be at any index from 52 to 104.
The number of possible values for $k$ (the index of the maximum element) is the count of leaf nodes.
Number of leaf nodes = $N - \lfloor N/2 \rfloor = 105 - 52 = 53$.
Thus, there are 53 possible values for $k$.

A max-heap property states that for every node $i$ other than the root, the value of node $i$ is less than or equal to the value of its parent. In an array representation, for an element at index $i$, its children are at $2i$ and $2i+1$.
Let's check option (b): 23, 17, 14, 7, 13, 10, 1, 5, 6, 12.
The root is 23.
Children of 23 are 17 and 14. (23 >= 17, 23 >= 14) - OK.
Children of 17 are 7 and 13. (17 >= 7, 17 >= 13) - OK.
Children of 14 are 10 and 1. (14 >= 10, 14 >= 1) - OK.
Children of 7 are 5 and 6. (7 >= 5, 7 >= 6) - OK.
Children of 13 is 12. (13 >= 12) - OK.
All other nodes are leaves. All parent-child relationships satisfy the max-heap property.
Let's quickly check other options for violations.
(a) 23, 17, 10, 6, 13, 14, 1, 5, 7, 12. Child 14 (index 6) is greater than parent 10 (index 3). Violation.
(c) 23, 17, 14, 6, 13, 10, 1, 5, 7, 15. Child 15 (index 10) is greater than parent 13 (index 5). Violation.
(d) 23, 14, 17, 1, 10, 13, 16, 12, 7, 5. Child 17 (index 3) is greater than parent 14 (index 2). Violation.

For a max-heap data structure, the Insert(A, key) operation involves adding a new element and then performing heapify-up to maintain the heap property. In the worst case, this requires traversing up the height of the heap, which is $O(\log n)$.
The Extract-Max(A) operation involves removing the root (maximum element), replacing it with the last element, and then performing heapify-down. In the worst case, this requires traversing down the height of the heap, which is also $O(\log n)$.
Therefore, both operations have a worst-case time complexity of $O(\log n)$.

In a binary min-heap, the minimum element is always at the root. However, the maximum element can be any of the leaf nodes. A binary heap has approximately $n/2$ leaf nodes. To find the maximum element, one must traverse all leaf nodes and compare their values. In the worst case, this requires checking all $n/2$ leaf nodes. Therefore, the time complexity is $\Theta(n)$.

To find the maximum element in a min-heap, we must examine all leaf nodes because the minimum element is at the root, and all other elements are greater than or equal to their children.

1. In an array representation of a binary heap with $N$ elements, the leaf nodes are found from index $\lfloor N/2 \rfloor + 1$ to $N$.
2. Given $N = 1023$ elements, the leaf nodes are located from index $\lfloor 1023/2 \rfloor + 1 = 511 + 1 = 512$ to $1023$.
3. The number of leaf nodes is $N - (\lfloor N/2 \rfloor) = 1023 - 511 = 512$.
4. To find the maximum among these $512$ leaf nodes, we need to compare all of them. The minimum number of comparisons to find the maximum among $k$ elements is $k-1$.
5. Therefore, $512 - 1 = 511$ comparisons are required.

[CORRECT_OPTION: 511]

I. True. In a max-heap, a parent node is always greater than or equal to its children. This property implies that values generally decrease as one moves down the tree, so the smallest element must be at a leaf.
II. True. The largest element is at the root. The second-largest element must be a child of the root, because any other node would be smaller than its parent, which in turn is smaller than or equal to the root.
III. True. We can obtain the elements from the BST in an array in $O(n)$ time (e.g., via level-order traversal). Then, the standard linear-time build-heap algorithm can construct a max-heap from this array in $O(n)$ time.
IV. False. Constructing a BST from a max-heap requires sorting the elements, which takes $\Omega(n \log n)$ time using heapsort.

Initial binary-max heap: $[25, 14, 16, 13, 10, 8, 12]$.
1st Deletion: Remove root $25$, move the last element $12$ to the root, resulting in $[12, 14, 16, 13, 10, 8]$. Heapify down by swapping $12$ with $16$ to maintain the max-heap property: $[16, 14, 12, 13, 10, 8]$.
2nd Deletion: Remove root $16$, move the last element $8$ to the root, resulting in $[8, 14, 12, 13, 10]$.
Heapify down (Step 1): Compare root $8$ with children $14$ and $12$. Swap $8$ with $14$: $[14, 8, 12, 13, 10]$.
Heapify down (Step 2): Compare $8$ with children $13$ and $10$. Swap $8$ with $13$ to complete the heap: $[14, 13, 12, 8, 10]$.

The number of min-heaps that can be formed from N distinct elements can be calculated using a recurrence relation. A min-heap with 7 nodes has a root, a left subtree of 3 nodes, and a right subtree of 3 nodes.

1. The smallest element, 1, must be at the root.
2. From the remaining 6 elements {2,3,4,5,6,7}, we must choose 3 for the left subtree. This can be done in $\binom{6}{3}$ ways.
3. Let T(n) be the number of min-heaps with n nodes. The total number of heaps is given by:
   $T(7) = \binom{6}{3} \times T(3) \times T(3)$
4. For a 3-node heap, we choose 1 element for the left child from the 2 available elements: $T(3) = \binom{2}{1} \times T(1) \times T(1) = 2$.
5. Substituting back: $T(7) = 20 \times 2 \times 2 = 80$.

Thus, there are 80 possible min-heaps.

To delete an element at index i in a binary heap, the standard algorithm replaces it with the last element of the heap. Then, the heap size is decremented. The new element at index i might violate the heap property. To restore it, the element is either sifted up (compared with its parent) or sifted down (compared with its children) until its correct position is found. In the worst-case scenario, this element might need to travel from the root to a leaf (or vice-versa), a path of length equal to the heap's depth, d. Therefore, the time complexity is O(d).

In a min-heap, any node's value must be greater than or equal to its parent's value. The question asks for the maximum possible depth for the integer 9. The root is at depth 0.
To maximize the depth of the node containing 9, we must place the 8 smaller integers {1, 2, 3, 4, 5, 6, 7, 8} on the path from the root to that node.
This creates a path where each node is the parent of the next integer in the sequence:
1 (root, depth 0) $\rightarrow$ 2 (depth 1) $\rightarrow$ 3 (depth 2) $\rightarrow \dots \rightarrow$ 8 (depth 7).
The integer 9 can then be a child of 8, placing it at depth 8. This structure is valid as the min-heap property is maintained along this path.

To convert the given array into a max-heap, we need to ensure that every parent node is greater than its children. The initial array represented as a tree violates this property. The PDF solution identifies a sequence of 3 swaps to fix this. The element 100 is the largest but is initially a leaf node.

1. Swap 100 with its parent, 15.
2. Swap 100 with its new parent, 50.
3. Swap 100 with its new parent, 89.
   This process moves the largest element, 100, to the root position, satisfying the heap property for the nodes in its path. This requires a minimum of 3 interchanges.

The tree has a root whose left and right subtrees are already max-heaps. To convert the entire tree into a max-heap, we only need to fix the potential violation at the root. This is achieved by a single call to the max-heapify (or sift-down) procedure on the root node. The time complexity of max-heapify is proportional to the height of the tree, which is $O(\log n)$. Thus, the lower bound for the number of operations is $\Omega(\log n)$.

To insert a new value into a max heap, the value is first added to the end of the array, which corresponds to the next available leaf position in the tree. The new value, 35, is then compared with its parent. If it is greater than its parent, they are swapped. This "bubble-up" process continues until the new value is less than or equal to its parent, or it becomes the root. In this case, 35 is first swapped with its parent 15, and then with its new parent 30. The process stops as 35 is less than its next parent, 40, thus restoring the max-heap property.

A Max-Heap maintains that the value of each node is greater than or equal to the value of its children. The level-order traversal shows the heap initially as: 10, 8, 5, 3, 2.

1. Insert 1: '1' is added as the next available leaf node. The heap structure becomes 10, 8, 5, 3, 2, 1. Since $1 < 2$, the max-heap property is maintained.
2. Insert 7: '7' is added as the next available leaf node, becoming a child of '3'. The heap is now 10, 8, 5, 3, 2, 1, 7.
3. Heapify for 7: Compare '7' with its parent '3'. Since $7 > 3$, swap them. The heap becomes 10, 8, 7, 3, 2, 1, 5.
4. Compare '7' with its new parent '8'. Since $7 < 8$, the max-heap property is now satisfied.
5. The final level-order traversal is 10, 8, 7, 3, 2, 1, 5.

To identify a max-heap, we must check if every parent node's value is greater than or equal to the values of its children.

Let's examine each option:

• Option A: Node 8 is a child of 10 (8 < 10), and 6 is a child of 10 (6 < 10). Node 4 is a child of 8 (4 < 8), and 5 is a child of 8 (5 < 8). Node 1 is a child of 6 (1 < 6), and 2 is a child of 6 (2 < 6). This structure satisfies the max-heap property.
• Option B: Node 8 is a child of 10 (8 < 10), and 6 is a child of 10 (6 < 10). Node 4 is a child of 8 (4 < 8), and 5 is a child of 8 (5 < 8). Node 1 is a child of 6 (1 < 6), and 2 is a child of 6 (2 < 6). This structure also satisfies the max-heap property.
• Option C: Node 10 is a child of 5 (10 > 5). This violates the max-heap property, as a child's value is greater than its parent's.
• Option D: Node 8 is a child of 2 (8 > 2). This violates the max-heap property.

Both A and B appear to be max-heaps based on the property. However, a heap is also a complete binary tree. Let's re-examine the definition from the PDF, which states "Heap is a complete binary tree".

• Option A is not a complete binary tree because level 3 is not filled from left to right (node 1 is missing its right sibling, and node 2 is also missing its right sibling, but the tree then continues with children of 6).
• Option B is a complete binary tree because all levels are filled, and the last level is filled from left to right. It also satisfies the max-heap property.

A binary max-heap ensures that every parent node is greater than or equal to its children. For an array representation, an element at index $i$ has children at $2i+1$ (left) and $2i+2$ (right).

1. Option A: $\{25,12,16,13,10,8,14\}$. Node $12$ (index $1$) has children $13$ (index $3$) and $10$ (index $4$). Since $12 < 13$, it violates the max-heap property.
2. Option B: $\{25,14,13,16,10,8,12\}$. Node $14$ (index $1$) has children $16$ (index $3$) and $10$ (index $4$). Since $14 < 16$, it violates the max-heap property.
3. Option C: $\{25,14,16,13,10,8,12\}$.
   • $25 \geq 14$ and $25 \geq 16$.
   • $14 \geq 13$ and $14 \geq 10$.
   • $16 \geq 8$ and $16 \geq 12$.
     All nodes satisfy the max-heap property.
4. Option D: $\{25,14,12,13,10,8,16\}$. Node $12$ (index $2$) has children $8$ (index $5$) and $16$ (index $6$). Since $12 < 16$, it violates the max-heap property.

Thus, only option C represents a binary max-heap.