Implement a Priority Queue using a Heap

A Priority Queue is an abstract data type where elements are dequeued based on priority rather than FIFO order. We typically implement this efficiently using a Binary Heap, which is a complete binary tree satisfying the heap property. In a Min-Heap, every parent node is less than or equal to its children, ensuring the smallest element is always at the root. Conversely, a Max-Heap ensures the largest element is at the root. To implement this, we use a dynamic array. This allows us to calculate child indices directly from the parent index without explicit pointers, saving significant memory overhead—a detail Microsoft values for scalable systems. For insertion, we append the new element to the end of the array to maintain completeness, then perform a sift-up operation. We compare the new element with its parent; if it violates the heap property, we swap them and repeat up the tree. This takes O(log n) time because the height of a complete binary tree is logarithmic relative to the number of elements. For deletion, specifically removing the highest priority item, we extract the root. To preserve the tree structure, we move the last element in the array to the root position and then perform a sift-down operation. We compare the current node with its children and swap with the smaller (in a Min-Heap) or larger (in a Max-Heap) child if necessary, repeating until the heap property is satisfied. This also runs in O(log n) time. Accessing the top element remains O(1), making this ideal for real-time task scheduling or Dijkstra's algorithm implementations.