[Solved] How do i get the reference to the last (yet unfilled) element in a binary tree? [closed]

by


In the discussion below, I demonstrate using a min-heap. A max-heap works the same way, except the root is the largest node rather than the smallest, and parents are larger than their children. Things work the same way, except that you reverse the sense of the comparisons.

Insertion into a binary heap follows these rules:

  1. Add the new item to lowest, left-most position.
  2. If the item is smaller than its parent, swap it with its parent.
  3. Repeat step 2 until the item is not smaller than its parent.

So let’s take the items [7,4,3,1].

You add the first one to the heap as the root, then you add the 4 as the root’s left child, giving.

    7
  4

4 is smaller than 7, so swap it with its parent.

    4
  7

The next value, 3, goes onto the heap in the first open position:

   4
 7   3

3 is smaller than 4, so we swap with the parent, resulting in the heap:

   3
 7   4

Finally, we add 1 to the lowest, left-most slot:

      3
    7   4
  1

1 is smaller than 7, so we swap the nodes:

      3
    1   4
  7

And 1 is smaller than 3, so we swap again:

      1
    3   4
  7

The resulting array representation of the binary heap is [1,3,4,7].

Original answer

This answer was based on the question title asking how to turn an array into a binary heap.

The method that transforms an array into a binary heap works by moving nodes down the heap into their proper positions. Let me illustrate with an example.

Start with an array, [7,4,3,6,1,2,5]. Displayed as a binary heap, it would be:

             7
           4   3
          6 1 2 5

Obviously, that isn’t a binary min heap. What you do is start at the level directly above the leaf level, and start moving nodes down if required.

So we start with 4. If it is larger than either of its children, then swap it with its smallest child. You end up with:

             7
           1   3
          6 4 2 5

Do the same thing with 3. It’s larger than 2, so swap it:

             7
           1   2
          6 4 3 5

And, finally, we have to move the 7. It’s larger than 1 and 2. We swap it with the smaller for the two, giving:

             1
           7   2
          6 4 3 5

7 is still larger than its children, so we swap it with the smaller of the two:

             1
           4   2
          6 7 3 5

And there’s your heap. The resulting array is [1,4,2,6,7,3,5].

2

solved How do i get the reference to the last (yet unfilled) element in a binary tree? [closed]