title: Can I have a heap-like contiguous layout for complete trees based on a depth first order rather than breadth first?
body: <p>The heap is a classical data structure that puts a complete binary (or d-ary for the generalized version) tree into a contiguous array, storing the elements in breadth-first traversal order. In this way, all elements from the same level of the tree are stored contiguous one after the other.</p>
  
  <p>I'm implementing a data structure which, under the hood, is a complete balanced tree of fixed degree d, and I want to store the tree in a contiguous form to free the space of node pointers. So I thought of putting the nodes into the breadth-first order used in heaps, but then I'm worried about cache performance of a typical search from the root down to a leaf, since at each level l, I jump over a lot of elements. </p>
  
  <p>Is there a way to obtain compact contiguous representation of a d-ary complete tree, based on depth-first order instead? </p>
  
  <p>This way, the nodes touched during a search of a leaf seem to me more likely to be found closer to each other. The problem then is how to retrieve the index of the parent and children of a node, but also I'm wondering which operations on the tree are in general efficient in this setting.</p>
  
  <p>I'm implementing this thing in C++, in case it matters at all.</p>