Why I Stop Sorting and Start Heaping: A Practical Guide to Priority Queues
Quick context (why you're writing this)
I was grinding through LeetCode’s “Kth Largest Element in an Array” for the umpteenth time. My first instinct? nums.sort() and grab the element at len(nums)-k. It worked, but I kept getting feedback that my solution was “not optimal” for large inputs. I spent a couple of hours staring at the editor, wondering why I kept reaching for the sort hammer when a screwdriver was sitting right there. Turns out, the screwdriver is a heap (or priority queue) and it lets us solve the problem in O(n log k) time while using only O(k) extra space. Once I saw that, a bunch of other interview questions started to make sense instantly.
The Insight
A heap isn’t just a fancy way to get the min or max element; it’s a data structure that lets you maintain a dynamic set of the k best (or worst) items seen so far, with each insertion or removal costing only logarithmic time.
