What is the logic behind inserting values into binary heaps (when build one)?

I have a midterm exam next week and am having difficulty drawing out a binary heap. The invariant for a minimum binary heap is: the value of the item stored at a parent node is always less than (greater than) the values of the items stored at its child nodes. The part that I don't understand is when I am inserting values into the heap, how do I know whether to go left or right? I'd really like to see step by step solutions, because I just don't understand how I would know whether to go left or right.

Say I have the values: 5, 8, 13, 15, 1, 2, 12, 4 it would start like

  5 then I insert 8
 / \ 
8? 13? is this going in the right direction?

I know for binary search trees the invariant is left< parent < right, but I am just really confused on how to determine whether to go left or right.

Solution

You choose the direction to ensure the underlying tree is a complete binary tree:

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible

Let's apply the trickle-up method to an example. Suppose you want to add a new element e to a heap. If the heap looks like this:

     5                                    5
   /   \                                /   \    
  6     9    add as right-child-->     6     9     then trickle-up
 / \   / \     to complete the        / \   / \
7                    tree            7   e

Then you add the new element as the right-child of the 6 and trickle-up (i.e. repeatedly swap the new element with its parent until the heap invariant is restored).

On the other hand, if the heap looks like this:

     5                                   5
   /   \                               /   \    
  6     9   add as left-child -->     6     9     then trickle-up
 / \   / \   to complete the         / \   / \
7  10              tree             7  10 e

Then you add the newest element as the left-child of the 9 and trickle up.

As for your example, the add sequence is 5, 8, 13, 15, 1, 2, 12, 4. The following code snippet shows the insert/trickle-up step-by-step:

    Add 5:

    	5

    No change due to trickle, So add 8:
    	
    	  5
    	 /
    	8
    	
    No change due to trickle-up. So, add 13:

          5
    	 / \
    	8  13
    	
    No change due to trickle-up. So, add 15:
    	    5
    	   / \
    	  8  13
    	 / 
    	15

    No change due to trickle-up. So, add 1:
    	
    	    5
    	   / \
    	  8  13
    	 / \
    	15  1
    	
    Then trickle-up:
    	
    	    1
    	   / \
    	  5  13
    	 / \
    	15  8

    Next, add 2:
    	
    	      1
    	   /     \
    	  5      13
    	 / \    /
    	15  8  2
    	
    Then trickle-up
    	
    	      1
    	   /     \
    	  5       2
    	 / \     /
    	15  8   13
    	
    Next, add 12:

    	      1
    	   /     \
    	  5       2
    	 / \     / \
    	15  8   13 12
    	
    No change due to trickle-up. So, add 4:

                1
    	     /     \
    	    5       2
    	   / \     / \
    	  15  8   13 12
    	 /
    	4
    	
    Then trickle-up:
    	
    	        1
    	     /     \
    	    4       2
    	   / \     / \
    	  5  8   13 12
    	 /
    	15