Priority Queue using Heaps

Hard
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.

Answer

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.")