Insertion into a binary heap

Insertion into a heap must maintain both the complete binary tree structure and the heap order property. To do this what we do is the following.

We know that in order to maintain the complete binary tree structure, we must add a node to the first open spot at the bottom level. So we begin by adding a node without data there. After that what we do is we see if inserting our new value will violate the heap property. If it doesn't put it in and we are done. Otherwise, we move the value from the parent of the empty node down , thus creating an empty node where the parent use to be. We again check to see if inserting the value violates the heap order property. If not, we add it in. Otherwise repeat the process until we are able to add the value. This process of moving the empty node towards the root is called percolate up

Illustrated example:

Insert into a heap the following values in order: 10,6,20,5, 16, 17, 13,2

We will use smaller values has higher priority as our priority ordering.

insert 10:

insert 6:

insert 20:

insert 5:

insert 16:

insert 17:

insert 13:

insert 2: