Why does an implicit array heap outperform a node-per-element pointer tree in a hot loop?

## Two layouts, identical asymptotics Both an implicit array heap and an allocated node-per-element tree give O(log n) per insert or removal, O(1) peek, and O(n) space. If you stop at the complexity class, they are the same structure. On real hardware they are not close, and the gap is a constant factor that routinely reaches several times. ## What the implicit layout removes **Per-node references.** A node object holds a left link, a right link, often a parent link, and the key. The implicit heap holds the key. For small keys — a rating and an identifier — the pointer version can be three to four times the bytes for the same data. More memory means more cache lines touched for the same work. **Per-node allocation.** Each node in the pointer version is an individual allocation with its own header and its own lifetime. Inserting means allocating; removing means freeing. The implicit version writes a slot. Under churn — a matchmaking pool taking hundreds of joins and pops per second — that difference alone is measurable, and it also removes the fragmentation that scatters nodes further apart over time. **Dependent loads.** This is the deepest effect. In a pointer tree, to visit a child the processor must first *have* the parent node in a register, because the child's address lives inside it. Each step is a load whose address depends on the previous load's result, so misses cannot overlap: the latencies add up in series. In the implicit heap the index of any descendant is pure arithmetic on `i` — you can compute `2i+1`, `2i+2`, or an address several levels down, before the current value has even arrived. Prefetchers and out-of-order execution have something to work with. **Layout drift.** Nodes allocated at different times end up wherever the allocator put them, so a pointer tree's physical layout has nothing to do with its logical shape and degrades as the structure ages. An array's layout is its shape, permanently. ## Where the advantage tapers, stated honestly Locality is excellent near the root and decays with depth. Levels 0 through about 4 hold 31 nodes — for small keys that is one or two cache lines, and since every operation touches the root and its immediate neighbourhood, those lines stay hot permanently. Below that, the indices `2i+1` and `2i+2` diverge exponentially, so consecutive steps of a deep path land in different lines and eventually different pages: a large heap costs roughly **one cache miss per level** for the deep part of a path, the same order as the pointer version, minus the dependent-load serialization. This is exactly why cache-aware variants exist. A d-ary heap (children at `di+1 .. di+d`) makes the tree shallower and puts all d children of a node adjacent, so one line fetch serves a whole comparison round — fewer levels, more comparisons per level, and usually a win for d of 4 or 8 on modern hardware. Cache-oblivious and van Emde Boas layouts go further, grouping subtrees rather than levels. ## What the implicit layout costs you - **Contiguity.** The whole structure needs one block. Growth typically doubles capacity and copies, which is amortized O(1) per insertion but produces a **latency spike** on the operation that triggers it — a real concern if the matchmaking loop has a tail-latency budget. Pre-sizing to the expected pool avoids it. - **Moving elements.** Repairs relocate elements between slots, so an index recorded now may name a different record later. Anything needing to adjust or remove a specific queued record must maintain a separate map from record identity to current slot, kept in step with every move — real complexity that the pointer version, where a node's address is stable, does not have. - **All-or-nothing memory.** A very large heap may fail to find a contiguous block where a pointer tree of the same total size would fit into fragmented space. ## How to say this in an interview Lead with the asymptotic equality, then be specific about the constants: bytes per element, allocations per operation, and dependent loads versus computed indices. Name the taper — locality is a top-of-the-heap effect, not a uniform one — and finish with the two prices, growth spikes and unstable positions. Claiming the array version is simply "faster" without the mechanism, or without the caveats, is the answer that does not distinguish a candidate.