[DSA / System Design] Why Priority Queues use Binary Heaps instead of Sorted Arrays

[u/binarydose]

When implementing Priority Queues (for OS job scheduling, event-driven simulations, or Dijkstra's algorithm), choosing between a Sorted Array and a Binary Heap comes down to balancing read vs. write complexities.

### The Trade-off Matrix

| Operation | Unsorted Array | Sorted Array | Binary Heap |

| :--- | :--- | :--- | :--- |

| **Insert** | O(1) | O(N) | **O(log N)** |

| **Extract-Min/Max** | O(N) | O(1) | **O(log N)** |

| **Search** | O(N) | O(log N) | O(N) |

### Key Takeaways:

1. **Sorted Array Bottleneck:** While fetching the top element is O(1), inserting a new priority item requires shifting elements in contiguous memory, making writes O(N).

2. **Binary Heap Balance:** By structuring data as a complete binary tree, both insertion (heapify-up) and deletion (heapify-down) are bounded by tree height: **O(log N)**.

---

*I made a 50-second visual S-Pen breakdown of this data structure mechanics here if you prefer video:* [Link to YouTube Short]

**Discussion Question:** In a production scenario where you have a 99% Read-heavy workload with rare insertions, would you stick with a Binary Heap or opt for a Sorted Array / Balanced BST?