fa © © oonrosm in19 Sec G)+ Which data structure is best suited for implementing a priority...
Fujitsu technical mcq question, verified with a worked answer. Free to practise - no sign-up.
fa © © oonrosm in19 Sec G)+ Which data structure is best suited for implementing a priority queue efficiently, especially in scenarios with dynamic updates? - A) Array - B) Linked List - C) Binary Heap - D) AVL Tree
Show answer & explanation
A Binary Heap is specifically designed to provide efficient access to the element with the highest (or lowest) priority. It allows for insertion and deletion of the priority element in logarithmic time, making it superior to linear structures for dynamic updates.
Step-by-step Derivation:
Step 1: Analyze the requirements of a Priority Queue. The primary operations are 'insert' and 'extract-max/min'.
Step 2: Evaluate Option A (Array): Insertion is O(1) if unsorted, but extraction is O(n). If sorted, insertion is O(n) and extraction is O(1).
Step 3: Evaluate Option B (Linked List): Similar to arrays, either insertion or extraction will take O(n) time to maintain order.
Step 4: Evaluate Option C (Binary Heap): A complete binary tree where the parent is always greater than or equal to its children. Insertion takes O(log n) and extraction of the root takes O(log n) due to the heapify process.
Step 5: Evaluate Option D (AVL Tree): While it supports O(log n) operations, it is a general-purpose balanced BST. It carries more overhead (pointers and balance factors) than a heap and is not the standard specialized structure for priority queues.
Step 6: Conclusion: The Binary Heap provides the optimal balance of time complexity and space efficiency for the specific operations of a priority queue.