title: Finding last element of a binary heap
body: <p><em>quoting <a href="http://en.wikipedia.org/wiki/Binary_heap#Heap_implementation" rel="noreferrer">Wikipedia</a>:</em></p>
  
  <blockquote>
    <p>It is perfectly acceptable to use a
    traditional binary tree data structure
    to implement  a binary heap. There is
    an issue with finding the adjacent
    element on the last level on the
    binary heap when adding an element
    which can be <em>resolved</em>
    <em>algorithmically</em>...</p>
  </blockquote>
  
  <p>Any ideas on how such an algorithm might work?</p>
  
  <p>I was not able to find any information about this issue, for most binary heaps are implemented using arrays.</p>
  
  <p>Any help appreciated.</p>
  
  <hr>
  
  <p>Recently, I have registered an OpenID account and am not able to edit my initial post nor comment answers. That's why I am responding via this answer. Sorry for this.</p>
  
  <hr>
  
  <p><em>quoting Mitch Wheat:</em></p>
  
  <blockquote>
    <p>@Yse: is your question "How do I find
    the last element of a binary heap"?</p>
  </blockquote>
  
  <p>Yes, it is.
  Or to be more precise, my question is: "How do I find the last element of a <em>non-array-based</em> binary heap?".</p>
  
  <p><em>quoting Suppressingfire:</em></p>
  
  <blockquote>
    <p>Is there some context in which you're
    asking this question? (i.e., is there
    some concrete problem you're trying to
    solve?)</p>
  </blockquote>
  
  <p>As stated above, I would like to know a good way to "find the last element of a non-array-based binary heap" which is necessary for insertion and deletion of nodes.</p>
  
  <p><em>quoting Roy:</em></p>
  
  <blockquote>
    <p>It seems most understandable to me to
    just use a normal binary tree
    structure (using a pRoot and Node
    defined as [data, pLeftChild,
    pRightChild]) and add two additional
    pointers (pInsertionNode and
    pLastNode). pInsertionNode and
    pLastNode will both be updated during
    the insertion and deletion subroutines
    to keep them current when the data
    within the structure changes. This
    gives O(1) access to both insertion
    point and last node of the structure.</p>
  </blockquote>
  
  <p>Yes, this should work. If I am not mistaken, it could be a little bit tricky to find the insertion node and the last node, when their locations change to another subtree due to an deletion/insertion. But I'll give this a try.</p>
  
  <p><em>quoting Zach Scrivena:</em></p>
  
  <blockquote>
    <p>How about performing a depth-first
    search...</p>
  </blockquote>
  
  <p>Yes, this would be a good approach. I'll try that out, too. </p>
  
  <p>Still I am wondering, if there is a way to "calculate" the locations of the last node and the insertion point. The height of a binary heap with N nodes can be calculated by taking the log (of base 2) of the smallest power of two that is larger than N. Perhaps it is possible to calculate the number of nodes on the deepest level, too. Then it was maybe possible to determine how the heap has to be traversed to reach the insertion point or the node for deletion.</p>