Data Structures u0026 Algorithms: Heaps u0026 Priority Queues Quiz

Test your expertise on data structures focusing on heaps and priority queues, including their algorithms and advanced operations. Deepen your understanding of heap-related algorithms through complex, scenario-based questions.

1. Min Heap Property Violation

   In an array-based binary min heap represented as [2, 4, 8, 10, 7, 9, 12, 15], which parent-child relationship explicitly violates the min heap property if the array corresponds to a complete binary tree starting from index 0?

   1. Parent 4 and child 7
   2. Parent 4 and child 8
   3. Parent 7 and child 10
   4. Parent 8 and child 12
   5. Parent 2 and child 4

2. Heapify Process Order

   During bottom-up heap construction (heapify) of the array [7, 3, 5, 1, 9, 8, 4], which root index is processed first to maintain efficient build time in a binary max heap?

   1. Index 2
   2. Index 3
   3. Index 1
   4. Index 0
   5. Index 5

3. Heap Sort Space Complexity

   When implementing heap sort in-place on an integer array, what is the worst-case additional space complexity, excluding input storage?

   1. O(n^2)
   2. O(1)
   3. O(log n)
   4. O(n)
   5. O(n log n)

4. Kth Largest in Unsorted Stream

   If you need to continuously find the kth largest element from a stream of unsorted integers of unknown length, which data structure provides the most optimal time complexity per insertion for this task?

   1. Sorted array
   2. Max Heap of size n
   3. Balanced binary search tree
   4. Min Heap of size k
   5. Min Heap of size n

5. Heap Insertion Time Analysis

   What is the maximum number of swaps that may occur when inserting a new element into a binary heap of height h?

   1. 2h
   2. h
   3. h + 1
   4. n/2
   5. log h

6. D-Ary Heap Children Calculation

   In a d-ary heap stored as an array with zero-based indexing, what is the formula to determine the index of the jth child of node at index i (where 1 ≤ j ≤ d)?

   1. i * d + j
   2. d * i + j
   3. i + d + j
   4. d * i + j - 1
   5. d * (i + 1) + j

7. Heap Sort Application on Partially Sorted Data

   Given an almost-sorted array in which only k elements are misplaced, which sorting algorithm would likely outperform heap sort in average case when k is much less than n?

   1. Heap sort
   2. Insertion sort
   3. Selection sort
   4. Bubble sort
   5. Counting sort

8. Max Heap Extraction Impact

   After extracting the maximum element from a max heap of n elements and restoring the heap property, what is the number of possible swap operations performed in the worst case?

   1. O(n)
   2. O(√n)
   3. O(n log n)
   4. O(1)
   5. O(log n)

9. Heap Construction Complexity

   What is the tightest time complexity for heapifying an array of n unordered elements (building a heap using the bottom-up approach)?

   1. O(n)
   2. O(n log n)
   3. O(1)
   4. O(n^2)
   5. O(log n)

10. Priority Queue Stability

    In a priority queue implemented with a binary heap, what is the behavior regarding identical priority elements (i.e., their insertion order) when they are removed?

    1. Removed in reverse of insertion order
    2. Removal order is not guaranteed (not stable)
    3. Removed in random order
    4. Always removed in order of smallest data value
    5. Guaranteed stable removal (insertion order preserved)