Its about pragmatic efficiency.
The big-O notation tends to simplify many aspects of the machine that the algorithm is executing on. It leaves out the constant multipliers, and constant additions. It doesn't address that even those operations take variable amounts of time. Nor does it address the fact that implementations do not have an infinite/very very large N, but instead operate over particular ranges of N.
Heaps
A binary heap can be allocated as a single block of memory if the size of N is known. Even if not known a simple reallocation strategy of doubling the allocation is very efficient. Alternately the blocks can be designed to fit within a memory page having a well-known capacity, and then assembled into balanced block trees.
This has several advantages:
- Keeping the data-structure dense and co-located decreases the likely-hood of a cache miss at the processor level, or a page miss at the memory level - both slow overall execution.
- Organising the tree to follow a predictable memory addressing pattern permits the index to be calculated within the processor and does not require a memory load.
- By minimising the need to reserve memory, memory management book keeping overheads are reduced.
And a few flaws:
A dense structure incurs an all or nothing memory overhead. An entire page/block must be allocated for even a heap of a single element.
Modification necessitates element copying - which may not be cheap. A complex object may have internal bookkeeping that is memory location dependent, and must be updated when moved/copied.
- If the capacity of the heap is exceeded a costly re/allocation operation must be performed.
Trees
Conversely a tree is generally constructed of nodes which are individually small in size and the nodes are linked via memory addresses. Removing a node is as simple as redirecting the pointers around the removed node, notifying the memory book keeper that it is no longer needed, and then applying a re-balancing operation that adjusts those addresses to achieve a balanced tree.
This has its advantages:
- The tree has exactly the capacity for what is held.
- The tree can be allocated in highly fragmented memory spaces.
- No elements are copied when modifying the tree (excluding creating the node itself).
- Memory bookkeeping is paid as needed.
But has its disadvantages:
- Each node must at least identify its two children, and other book keeping state. Usually
3*sizeof(pointer).
- Tree traversal requires memory access to read the location, then another memory access to access the next node.
- Tree nodes are allocated sparsely increasing the chance of a cache-miss, or a page-miss
- Much more memory bookkeeping is required.
Simplifications
Note that I have simplified this significantly, and alternate implementation choices could be made:
- I could have used block allocation for the tree, forcing the elements of many nodes other than the one being manipulated to be copied around, while simplifying the rebalancing of the tree, and omitting storage/modification of node addresses.
- I could have used single element nodes for the heap, sacrificing memory density for minimal element copying.
These would have changed the trade-offs and the total cost of each. In a given context these changes would pay dividends, but outside of that context they hobble the use case with unnecessary work.
Specification
What is most efficient is situational. Thus it is usually best to specify the exact operations needed, and allow implementations to provide that operation in the most contextually efficient manner it can.
So as before if the operation is over expensive to copy objects, I probably would use a red-black tree to offer Heap operations, or some other similar low-copy data-structure.
Conversely if the data in the heap were single bytes, the block encoded binary heap is a clear winner: N * (1byte + 3*ptrsize bytes) vs. Nbytes.
