Virtual Labs

1. Which of the following arrays represents a valid min-heap after the insert-heap step is performed?

a: [1, 4, 3, 9, 2, 8, 6, 7] Explanation

Explanation

b: [2, 3, 9, 1, 6, 7, 4] Explanation

Explanation

c: [4, 1, 3, 9, 2, 8, 6, 7] Explanation

Explanation

d: [1, 9, 4, 2, 3, 8, 6, 7] Explanation

Explanation

2. What do you think is the complexity of inserting into a heap using this naive insert heap method? (Consider if it can be further improved)

O(n)

Explanation

O(\log n)

Explanation

O(n\log n)

Explanation

O(n^2)

Explanation

3. In a min-heap, where should a newly inserted element initially be placed before restoring the heap property?

a: At the root Explanation

Explanation

b: At any random position Explanation

Explanation

c: At the next available position at the end of the heap Explanation

Explanation

d: Always as the left child of the root Explanation

Explanation

4. What operation is used to restore the heap property after inserting a new element?

a: Sift-up (heapify-up) Explanation

Explanation

b: Merge Explanation

Explanation

c: Partition Explanation

Explanation

d: Linear search Explanation

Explanation

5. If the height of a binary heap is

O(\log n)

, what is the worst-case time complexity of standard heap insertion using sift-up?

O(1)

Explanation

O(\log n)

Explanation

O(n)

Explanation

O(n^2)

Explanation

6. Why is the complete-tree property important during heap insertion?

a: It ensures every element has the same value Explanation

Explanation

b: It guarantees the array is sorted Explanation

Explanation

c: It determines a valid next position while keeping the heap shape complete Explanation

Explanation

d: It removes the need for comparisons Explanation

Explanation

7. Suppose a min-heap contains the elements

[2, 4, 6, 8]

. If

1

is inserted and sift-up is performed, what will be the new root?

2

Explanation

4

Explanation

6

Explanation

1

Explanation

8. Which statement best distinguishes the naive insert-heap method from the standard efficient heap insertion?

a: The naive method never changes the array Explanation

Explanation

b: The standard method maintains the complete-tree shape and restores order along a root-to-leaf path in

O(\log n)

worst-case time Explanation

Explanation

c: The naive method always takes

O(n^2)

for one insertion Explanation

Explanation

d: The standard method requires sorting the entire array after every insertion Explanation

Explanation

9. If

n

elements are inserted one at a time into a heap using the standard

O(\log n)

insertion method, what is the worst-case upper bound for all insertions?

O(n)

Explanation

O(\log n)

Explanation

O(n^2)

Explanation

O(n\log n)

Explanation

Heap Sort