Heap, sorted list, or balanced tree for a live auction's top bid and next-k view?

## Start from the operation counts, not the structure names A live auction page needs two things from its bid store: the current highest bid, read on every render and every websocket push, and — when a viewer expands a panel — the next few bids below it, in order. Bids themselves arrive continuously, and occasionally a bid is retracted. Write the profile down before choosing: - insert: very high volume - read the single maximum: very high volume - read the next k in order: low volume, small k - delete an arbitrary element: rare but required - full ordering of everything: never That last line matters as much as the first. A structure that maintains total order pays for a property nobody reads. ## The three candidates against that profile **Sorted array.** Finding the insertion point is a binary search, O(log n), but placing the element shifts everything after it: O(n) per bid. The top is at a known end, O(1); the next k are the k adjacent entries, O(k), with excellent locality. It is genuinely the simplest code and the right answer for a read-mostly list — but here the highest-volume operation is exactly the one it does worst. On a hot auction with tens of thousands of live bids, every incoming bid moves memory proportional to the whole set. A sorted linked list is not a rescue: it removes the shifting but reintroduces an O(n) walk to find the insertion point, because there is no random access to binary-search over. **Binary max-heap.** A complete binary tree in an array, with the invariant that each node is at least as large as its children. Insert appends and sifts up, O(log n) worst case; the maximum is the root, O(1) to read. This matches the two high-volume operations precisely — which is the whole argument against the sorted list, and it is an argument about the profile rather than about elegance. The heap's weakness is exactly the operation the sorted list did well. The heap invariant is only parent-versus-child; siblings and cousins are unordered, so the array is *not* sorted and the second largest element is merely "one of the root's two children". Producing k items in descending order means repeatedly extracting the root, which mutates the structure — so you copy first and extract from the copy, roughly O(k log n) on top of the copy, or you run a bounded search over the top of the array. When k is 5 and the panel opens rarely, that is fine. When the panel is on every render, it is the wrong structure. Arbitrary deletion is the heap's other weak point: retracting a specific bidder's bid requires finding it, and nothing in the heap tells you where it is. The standard fix is a side map from bid identity to array position, kept updated on every sift — a second structure with an invariant to maintain, which is real complexity to hand to a team. **Balanced search tree.** Ordered by bid value with a balancing rule holding the height at O(log n). Insert and delete-by-key are O(log n); the maximum is the rightmost node, O(log n) to reach or O(1) if you cache a pointer and update it on mutation; the next k in descending order is a reverse in-order walk, O(log n + k), no copy and no mutation. It costs more per insert in constants than the heap and more memory per element, and it is more machinery than either alternative. | Operation | Sorted array | Binary max-heap | Balanced tree | | --- | --- | --- | --- | | insert a bid | O(n) shift | O(log n) | O(log n) | | read the top | O(1) | O(1) | O(log n), O(1) cached | | next k in order | O(k) | ~O(k log n) on a copy | O(log n + k) | | delete a named bid | O(n) | O(log n) with a side index | O(log n) | ## Defending the choice out loud The answer an interviewer wants is not a structure, it is a ratio: how often is the runners-up panel opened relative to bid arrivals, and are retractions in scope? If the panel is rare and retraction is handled by tombstoning rather than removal, the heap is defensible and simpler than a tree. If the panel is rendered with the top bid on every page — which product will ask for eventually — the tree wins on the operation that actually repeats, and the extra constant on insert is cheap next to copying a heap on every render. The sorted list keeps its constituency: a small auction, or a store rebuilt periodically rather than continuously mutated, where n stays in the dozens. At that size the shift is a memory move over a contiguous block and beats both alternatives on constants. "Simpler" is a legitimate argument — it just has to be attached to a bound on n and a measured insert rate, not asserted. ## The distinguishing move Weak answers name a structure first and justify it afterwards. Strong answers state the profile, note which operation has the highest volume, and only then choose — and they say what would change the choice. Here the switch condition is crisp: the moment the ordered runners-up view moves onto the render path, the heap stops fitting.