Interview Questions Programming Priority Queue Using Heaps

Priority Queue Using Heaps

Your task is to implement a Priority Queue using a binary heap data structure. The Priority Queue should support insertion, deletion, and retrieval of the element with the highest priority. To read more about the Priority Queue, check out the Hint button.

class PriorityQueue:

    def __init__(self):

        pass

    

    def insert(self, element: int) -> None:

        pass



    def delete(self) -> int:

        pass

    

    def peek(self) -> int:

        pass



    def _heapify_up(self) -> None:

        pass



    def _heapify_down(self) -> None:

        pass

Methods

__init__(): Initializes the Priority Queue.
insert(element: int): Inserts an element into the Priority Queue while maintaining the heap property.
delete(): Removes and returns the element with the highest priority (maximum value for max-heap, minimum value for min-heap).
peek() -> int: Returns the element with the highest priority without removing it from the Priority Queue.
_heapify_up(): Called after an insert operation. If the max heap condition is violated due to the newly inserted element, this method adjusts the heap to restore the max heap property.
_heapify_down(): Called after a delete operation. If the max heap condition is violated due to the swap and removal of the root, this method adjusts the heap to restore the max heap property.

Example

pq = PriorityQueue()

pq.insert(3)

pq.insert(1)

pq.insert(4)

print(pq.peek())  # Should return 4 if max-heap, 1 if min-heap

pq.delete()

print(pq.peek())  # Should return 3 if max-heap, 1 if min-heap

Note
You can assume that the delete() and peek() methods will not be called on an empty Priority Queue.

Hint

Priority Queue
A Priority Queue is an advanced data structure that extends the basic queue with the concept of priority. In a standard queue, elements are dequeued in the same order they are enqueued (First-In, First-Out). However, in a Priority Queue, each element is associated with a priority, and elements are dequeued based on their priorities, not the order in which they were added to the queue.

Here are five significant applications of Priority Queues in the trading industry:

Order Matching in Exchanges: Priority Queues can be used to manage buy and sell orders in a trading exchange. Orders can be prioritized based on various factors like price and time, ensuring that the highest-priority (e.g., highest-bid) orders are matched first.
Risk Management: Traders often use algorithms to assess the risk associated with different trading positions. A Priority Queue can be used to sort these positions based on their risk levels, allowing traders to focus on managing the highest-risk positions first.
Resource Allocation: In algorithmic trading, various algorithms may require different computational resources. A Priority Queue can be used to manage these algorithms, ensuring that the most crucial algorithms get the resources they need first.
Data Feeds: Financial markets produce massive amounts of data that need to be processed in real-time. Priority Queues can be used to manage this data, ensuring that the most critical data is processed first.
Event-Driven Strategies: In algorithmic trading, strategies can be based on market events like earnings announcements or economic reports. A Priority Queue can help manage these events, ensuring that the most impactful events are processed first to make timely trades.

Binary Heap
A binary heap is a complete binary tree that satisfies the heap property. In a complete binary tree, all levels except possibly the last are completely filled, and all nodes are as left as possible. The heap property means that the key stored in each node is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the keys of that node's children.

In a max heap, the maximum key is found at the root, while in a min heap, the minimum key is at the root. Binary heaps are commonly used to implement Priority Queues because they allow both insertion and deletion operations to be performed in O(logn) time, where n is the number of elements in the heap.

Here are some key characteristics of a binary heap:

Heap Operations: The primary operations associated with a binary heap are insert, delete (or extract-min/extract-max), and peek (get the minimum or maximum without removing it). These operations are generally O(logn) for a binary heap with n elements.
Array Representation: Binary heaps are usually represented as arrays. For a given node at index i, its left child is at index 2i+1 and its right child is at 2i+2.
Heapify: This is an operation that rearranges an array of elements into a heap. It's a key part of many algorithms that use heaps.
Balanced Tree: One of the reasons heaps are efficient is that they are balanced, meaning the height of the tree is minimized.

Let's consider an example of a max heap, where each parent node is greater than or equal to its children. Below is the tree representation and the corresponding array representation of a max heap.

Tree Representation:

         10

       /    \

      9      8

     / \    / \

    7   6  5   4

Array Representation:

[10, 9, 8, 7, 6, 5, 4]

In the array representation, the element at index 0 is the root of the heap. For any element at index i:

The left child is at index 2i+1. For example, for the root element at index 0, the left child is at 2×0+1=1, which is 9.
The right child is at index 2i+2. For the root element at index 0, the right child is at 2×0+2=2, which is 8.

The tree satisfies the max heap property, as every parent node is greater than or equal to its child nodes.

If the array is [10,9,5,7,6,8,4], then the corresponding binary tree would look like this:

         10

       /    \

      9      5

     / \    / \

    7   6  8   4

In this case, the tree does not satisfy the max heap property because there are parent nodes that are not greater than or equal to their children. Specifically, the node with value 5 has a child with value 8, and the node with value 5 is less than its child.

Thus, this tree is not a valid max heap. To convert it into a max heap, you would have to rearrange the nodes to satisfy the heap property. This process is often done through a series of "heapify" operations that restore the heap property for the tree.

Solution

class PriorityQueue:

    def __init__(self):

        self.heap = []

        

    def insert(self, element):

        self.heap.append(element)

        self._heapify_up()

        

    def delete(self):

        if len(self.heap) == 0:

            return None

        if len(self.heap) == 1:

            return self.heap.pop()

        

        root = self.heap[0]

        self.heap[0] = self.heap.pop()

        self._heapify_down()

        return root

    

    def peek(self):

        return self.heap[0] if self.heap else None

    

    def _heapify_up(self):

        index = len(self.heap) - 1

        while index > 0:

            parent_index = (index - 1) // 2

            if self.heap[index] > self.heap[parent_index]:

                self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]

                index = parent_index

            else:

                break

    

    def _heapify_down(self):

        index = 0

        while index < len(self.heap):

            left_child_index = 2 * index + 1

            right_child_index = 2 * index + 2

            

            # Find the maximum child index

            if left_child_index < len(self.heap) and right_child_index < len(self.heap): 

                max_child_index = left_child_index if self.heap[left_child_index] > self.heap[right_child_index] else right_child_index

            elif left_child_index < len(self.heap): 

                max_child_index = left_child_index 

            else: 

                break 



            # Swap if the child is greater than the parent

            if self.heap[max_child_index] > self.heap[index]:

                self.heap[max_child_index], self.heap[index] = self.heap[index], self.heap[max_child_index]

                index = max_child_index

            else:

                break





# Test the Priority Queue implementation

pq = PriorityQueue()

pq.insert(3)

pq.insert(1)

pq.insert(4)

assert pq.peek() == 4  # Should return 4 for max-heap

assert pq.delete() == 4  # Should return 4 for max-heap

assert pq.peek() == 3  # Should return 3 for max-heap



print("Priority Queue implementation is working correctly.")

Title	Category	Subcategory	Difficulty	Status
Circular Queue Implementation	Programming	Other	Hard	Unlock
Last Node of Singly Linked List	Programming	Other	Medium	Unlock
Weather API Data Analyzer	Programming	Other	Hard	Unlock

The Interview Guide for Quants and Traders

The Interview Guide for Quants and Traders