ยง 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, andright child is at 2*i+1. This gives parent at i//2.
  • 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 intothe middle: For example, an implicit treap where we wish to splice sub-arraystogether.
  • On coding a heap, we can decide whether to use the left or right sibling byusing next = 2*i + predicate. If predicate = false = 0, we will pickthe left child, otherwise the right child. This allows us to compresssome annoying if/then/elses into one-liners.