Heap Practice Questions

When inserting $n$ elements into a binary heap of $n$ elements, we can append the $n$ new elements to the underlying array, resulting in a total of $2n$ elements. Rather than performing $n$ individual insertions, which would take $\Theta(n \log n)$ time, we can apply the Build-Heap algorithm to the entire array of size $2n$. The Build-Heap algorithm constructs a valid binary heap from an arbitrary array in time proportional to the number of elements. Thus, the construction process for $2n$ elements runs in $\Theta(2n)$ time. Therefore, the total time complexity is $\Theta(n)$.

When inserting an element into a Max Heap, it is initially placed at the next available leaf position. The path from this new leaf to the root has a length equal to the height of the heap. For a heap with $n$ elements, the height is $\Theta(\log n)$.

Let $L$ be the length of this path. Thus, $L = \Theta(\log n)$.
Performing a binary search on a path of length $L$ requires $\Theta(\log L)$ comparisons.
Substituting the value of $L$, the number of comparisons is $\Theta(\log(\log n))$.

In a 3-ary heap, the children of a node at index $i$ are located at indices $3i+1$, $3i+2$, and $3i+3$. For Option D ([9, 5, 6, 8, 3, 1]$), we verify the max heap property (parent$≥$ children):

1. Root at index $0$ ($9$): Children are at $1, 2, 3$ ($5, 6, 8$). Since $9 \ge 5$, $9 \ge 6$, and $9 \ge 8$, the root satisfies the heap property.
2. Node at index $1$ ($5$): Children are at $4, 5$ ($3, 1$). Since $5 \ge 3$ and $5 \ge 1$, this node also satisfies the heap property.
3. Other options fail: A ($1 < 3$), B ($6 < 8$ at index $1$ and $4$), and C ($3 < 5$ at index $1$ and $4$).
   Thus, D is the only valid sequence.

A binary max-heap represented as an array $A$ of size $n$ must satisfy $A[i] \ge A[2i+1]$ and $A[i] \ge A[2i+2]$ for all valid indices.
For option C, the sequence is $\{23, 17, 14, 7, 13, 10, 1, 5, 6, 12\}$ with corresponding indices $0$ to $9$.
We verify the max-heap property:

• Parent $A[0]=23 \ge A[1]=17, A[2]=14$
• Parent $A[1]=17 \ge A[3]=7, A[4]=13$
• Parent $A[2]=14 \ge A[5]=10, A[6]=1$
• Parent $A[3]=7 \ge A[7]=5, A[8]=6$ and Parent $A[4]=13 \ge A[9]=12$
  All parent nodes are greater than or equal to their children, confirming this sequence forms a valid max-heap.

In a 3-ary max heap, the children of a node at index $i$ are located at indices $3i+1$, $3i+2$, and $3i+3$. The heap property requires that every parent node is greater than or equal to its children: $a[i] \ge \{a[3i+1], a[3i+2], a[3i+3]\}$.
For option A: $[10, 7, 9, 8, 3, 1, 5, 2, 6, 4]$, we verify the heap structure:

• Root at index $0$ ($10$): Children at $1, 2, 3$ are $\{7, 9, 8\}$. $10 \ge \{7, 9, 8\}$ is true.
• Index $1$ ($7$): Children at $4, 5, 6$ are $\{3, 1, 5\}$. $7 \ge \{3, 1, 5\}$ is true.
• Index $2$ ($9$): Children at $7, 8, 9$ are $\{2, 6, 4\}$. $9 \ge \{2, 6, 4\}$ is true.
  Since all parent-child relationships satisfy the max heap condition, this array represents the correctly structured 3-ary max heap after the insertions.

In a binary max heap, the property $A[parent(i)] \ge A[i]$ ensures the largest element is at the root, while the smallest element is guaranteed to reside among the leaf nodes.
In a complete binary tree with $n$ nodes, there are $\lceil n/2 \rceil$ leaf nodes located at indices from $\lfloor n/2 \rfloor + 1$ to $n$.
Because the max-heap structure imposes no specific ordering on the leaf nodes relative to one another, they can appear in any order.
To find the absolute minimum value, one must inspect all leaf nodes, as any of them could contain the smallest element.
Since checking $\lceil n/2 \rceil$ elements requires linear time, the complexity is $\Theta (n)$.

To insert elements into a Max-Heap, we place them at the next available position and "bubble up" to maintain the heap property ($parent \ge child$).
Initially, the heap is $[10, 8, 5, 3, 2]$.

1. Inserting $1$: It becomes the left child of $5$ (index 6). The array is $[10, 8, 5, 3, 2, 1]$. The heap property holds.
2. Inserting $7$: It is placed at index 7 (right child of $5$). The array becomes $[10, 8, 5, 3, 2, 1, 7]$.
3. Bubble up: Compare $7$ with its parent $5$. Since $7 > 5$, swap them. The array becomes $[10, 8, 7, 3, 2, 1, 5]$.
4. The new parent of $7$ is $10$. Since $7 < 10$, no further swaps are required.
   The final level-order traversal is $10, 8, 7, 3, 2, 1, 5$.

To build the MaxHeap, we insert elements one by one, performing a "bubble up" operation whenever a new element is larger than its parent:

1. Insert $32, 15, 20$: The heap is $\{32, 15, 20\}$.
2. Insert $30$: $30 > 15$, so swap $30$ and $15$. The heap becomes $\{32, 30, 20, 15\}$.
3. Insert $12$: The heap becomes $\{32, 30, 20, 15, 12\}$.
4. Insert $25$: $25 > 20$, so swap $25$ and $20$. The heap becomes $\{32, 30, 25, 15, 12, 20\}$.
5. Insert $16$: Since $16 < 25$, no further swaps are needed. The final tree structure with root $32$, children $30$ and $25$, and sub-children $15, 12$ and $20, 16$ matches figure (a).

The heap construction algorithm, often called Build-Heap, processes internal nodes from the last level up to the root, performing the heapify (or siftDown) operation on each. A node at height $h$ takes $O(h)$ time to heapify, and there are at most $\lceil n / 2^{h+1} \rceil$ nodes at any height $h$. The total time complexity is given by the sum:
$T(n) = \sum_{h=0}^{\lfloor \log n \rfloor} \frac{n}{2^{h+1}} O(h) = O\left( n \sum_{h=0}^{\infty } \frac{h}{2^h} \right)$
Since the infinite series $\sum_{h=0}^{\infty } \frac{h}{2^h}$ converges to $2$, the expression simplifies to $O(2n)$, which is $O(n)$. Therefore, constructing a heap from an array of size $n$ takes linear time.

In a min-heap, the $k^{th}$ smallest element must reside within the first $k$ levels of the tree. For $k=7$, the maximum number of nodes to examine is $2^k - 1 = 2^7 - 1 = 127$. Since $k$ is a fixed constant, searching through these $127$ potential candidates requires a constant number of comparisons. Because this search process does not depend on the total number of elements $n$, the time complexity is $\Theta(1)$.

To satisfy the requirements, the data structure must support searching for an existing element, inserting a new element, and deleting the minimum element, all in $O(\log n)$ time. A balanced binary search tree (BST) maintains elements in a sorted order, allowing both search and insertion to occur in $O(\log n)$ time, and the minimum element (the leftmost node) can also be deleted in $O(\log n)$ time. Conversely, while a heap supports $O(\log n)$ insertion and $O(\log n)$ deletion of the minimum, it does not support searching for the existence of an arbitrary element in $O(\log n)$ time; searching a heap typically requires $O(n)$ time. Therefore, only the balanced BST is suitable for these operations.

In an array representation of a binary heap using 1-based indexing, a node at index $p$ has a left child at index $2p$ and a right child at index $2p+1$. For any node at index $i > 1$, the parent index $p$ is determined by reversing these relations. If $i$ is even (left child), $i = 2p$, which implies $p = i/2$. If $i$ is odd (right child), $i = 2p + 1$, which implies $p = (i-1)/2$. Both cases are unified by the floor function, yielding $p = \lfloor i/2 \rfloor$.

To convert the array $[89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70]$ into a max-heap using Floyd's algorithm, we start at the last non-leaf node, index $i = \lfloor \frac{n-2}{2} \rfloor = 5$.

1. At index $5$ (value $10$), the children are at indices $11$ ($9$) and $12$ ($70$). Since $70 > 10$, swap $10$ and $70$ (Interchange 1).
2. Indices $4$ ($12$) and $3$ ($17$) already satisfy the max-heap property.
3. At index $2$ (value $40$), the children are index $5$ ($70$) and index $6$ ($2$). Since $70 > 40$, swap $40$ and $70$ (Interchange 2).
4. Checking the heap property at index $5$ (now $40$), the children are $9$ and $10$; no further swap is needed.
5. Indices $1$ and $0$ already satisfy the max-heap property, requiring no additional operations.
   Total interchanges required: $2$.