Implement Priority Queue with with follow-up

Question

Implement a Priority Queue data structure that supports the following operations: insert an element, delete the highest priority element, and retrieve the highest priority element, all in O(log n) time. Your implementation should handle integer priorities, and the output for the retrieval operation should be the element with the highest priority.

Codemia · Accepted Answer

The problem requires implementing a Priority Queue, which is a data structure that allows for efficient retrieval of the highest priority element. The specific operations we need to support are: inserting an element, deleting the highest priority element, and retrieving the highest priority element. The O(log n) time complexity for these operations suggests that we can utilize a binary heap (either min-heap or max-heap). In this case, a max-heap is appropriate since we want to efficiently access the highest priority element. The max-heap will maintain the property that the parent node is always greater than or equal to its children, allowing us to perform insertions and deletions in logarithmic time. 1. **Data Structure**: We'll use a max-heap to store elements along with their priorities. 2. **Insert Operation**: When inserting a new element, we add it to the end of the heap and then 'bubble it up' to its correct position to maintain the max-heap property. For example, if we insert (priority: 5, value: 'A'), it will be placed at the bottom. If there was a higher priority element above it, we swap them until the max-heap property is restored. 3. **Delete Operation**: To delete the highest priority element, we remove the root of the heap (the maximum element), replace it with the last element in the heap, and then 'bubble it down' to restore the heap property. For example, if we delete the root (priority: 10, value: 'B'), we replace it with (priority: 3, value: 'C') and then ensure the new root is repositioned correctly. 4. **Retrieve Operation**: To retrieve the highest priority element, we simply return the root of the heap without modifying it. For example, if the root is (priority: 10, value: 'B'), we return this element directly. ```python class PriorityQueue: def __init__(self): self.heap = [] # This will hold our heap elements in the form (priority, value) def insert(self, priority, value): self.heap.append((priority, value)) # Add the new element at the end self._bubble_up(len(self.heap) - 1) # Restore the max-heap property def delete(self): if not self.heap: return None # If the heap is empty max_element = self.heap[0] # The root is the max element self.heap[0] = self.heap[-1] # Move the last element to the root self.heap.pop() # Remove the last element self._bubble_down(0) # Restore the max-heap property return max_element def retrieve(self): return self.heap[0] if self.heap else None # Return the root of the heap without removing it def _bubble_up(self, index): parent = (index - 1) // 2 while index > 0 and self.heap[index][0] > self.heap[parent][0]: self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index] index = parent parent = (index - 1) // 2 def _bubble_down(self, index): while index < len(self.heap): left = 2 * index + 1 right = 2 * index + 2 largest = index if left < len(self.heap) and self.heap[left][0] > self.heap[largest][0]: largest = left if right < len(self.heap) and self.heap[right][0] > self.heap[largest][0]: largest = right if largest == index: break self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index] index = largest ``` The time complexity for each of the three operations (insert, delete, retrieve) is as follows: - **Insert**: O(log n) because we may have to bubble up the newly inserted element through the height of the heap. - **Delete**: O(log n) due to the bubbling down process that may need to traverse the height of the heap after removing the max element. - **Retrieve**: O(1) since we simply return the root element without modifying the heap. The space complexity is O(n) because we store up to n elements in the heap. 1. **Empty Queue**: If we call delete or retrieve on an empty priority queue, we should handle this gracefully, returning None or a similar indication of emptiness. 2. **Duplicate Priorities**: The implementation should correctly handle cases where multiple elements have the same priority, ensuring that they are retrieved in the order they were inserted. 3. **Large Values**: Ensure the implementation can handle the largest and smallest possible integers for priorities, confirming it doesn't break with extreme values.

Implement Priority Queue with with follow-up

Doordash

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

Doordash 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