§ Thoughts on implicit heaps
Some musings I had on the ability to represent heaps as arrays, and in general,
the benifits of knowing the total number of elements.
- Knowing the total number of elements allows us to pre-ordain a memory layout. We can decide that for a node at index
i, left child is at
2*i, and right child is at
2*i+1. This gives parent at
- This immediately gives us
O(1) access to parent (
i//2) and sibling
(i^1)with no extra memory usage. S
- This cannot be done for data structures where we need to splice into the middle: For example, an implicit treap where we wish to splice sub-arrays together.
- On coding a heap, we can decide whether to use the left or right sibling by using
next = 2*i + predicate. If
predicate = false = 0, we will pick the left child, otherwise the right child. This allows us to compress some annoying if/then/elses into one-liners.