Implement Priority Queue with with follow-up

Question

Implement a priority queue data structure that supports insert, delete, and retrieve operations, ensuring that the highest priority element can be accessed in O(log n) time. Your implementation should allow for the insertion of elements with associated priority values and should return the element with the highest priority when retrieved.

Codemia · Accepted Answer

To implement a priority queue that allows for efficient insertion, deletion, and retrieval of elements based on their priority, we can use a binary heap. This data structure supports the required operations in O(log n) time, which is ideal for this problem. A max-heap, in particular, will allow us to quickly access and remove the highest priority element, as the highest value is always at the root of the heap. The binary heap maintains a complete binary tree structure, ensuring that both insertion and deletion operations remain efficient. 1. **Define the Node Structure**: Create a class for the elements in the priority queue that holds both the value and its priority. 2. **Heap Implementation**: Use a list to represent the binary heap. The first element in the list will be the highest priority. 3. **Insert Operation**: Add the new element to the end of the list, then 'bubble up' to maintain the heap property by comparing with its parent until it finds its correct position. 4. **Delete Operation**: Remove the root (highest priority), replace it with the last element in the list, and then 'bubble down' to restore the heap property. 5. **Retrieve Operation**: Simply return the root element of the heap without modifying the structure. **Example**: If we insert (value=5, priority=1) and (value=10, priority=2), the heap will be structured as [10, 5] after both insertions, where 10 is the highest priority. ```python class Node: def __init__(self, value, priority): self.value = value self.priority = priority class PriorityQueue: def __init__(self): self.heap = [] def insert(self, value, priority): node = Node(value, priority) self.heap.append(node) self._bubble_up(len(self.heap) - 1) def _bubble_up(self, index): parent_index = (index - 1) // 2 if index > 0 and self.heap[index].priority > self.heap[parent_index].priority: self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index] self._bubble_up(parent_index) def delete(self): if not self.heap: return None if len(self.heap) == 1: return self.heap.pop().value root_value = self.heap[0].value self.heap[0] = self.heap.pop() self._bubble_down(0) return root_value def _bubble_down(self, index): largest = index left_index = 2 * index + 1 right_index = 2 * index + 2 if (left_index < len(self.heap) and self.heap[left_index].priority > self.heap[largest].priority): largest = left_index if (right_index < len(self.heap) and self.heap[right_index].priority > self.heap[largest].priority): largest = right_index if largest != index: self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index] self._bubble_down(largest) def retrieve(self): if not self.heap: return None return self.heap[0].value ``` The time complexity for both insert and delete operations in this priority queue implementation is O(log n) due to the nature of the binary heap. Each operation involves traversing the height of the heap, which is logarithmic relative to the number of elements. The retrieve operation is O(1) since it only accesses the root of the heap. The space complexity is O(n) as we store all elements in a list. 1. **Empty Priority Queue**: If both delete and retrieve operations are called on an empty priority queue, they should return None or raise an exception to handle the scenario gracefully. 2. **Single Element**: Inserting a single element and then performing delete should return that element, leaving the queue empty. 3. **Identical Priorities**: If multiple elements are inserted with the same priority, the order of retrieval should respect the order of insertion (FIFO for equal priorities).

Implement Priority Queue with with follow-up

Apple

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Apple Machine Learning Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string