Inserting a node in a min-heap with a null value at the end

Question

I got a sorted min-heap array: 2,3,4,5,NULL

I'd like to insert the value 1 in it, how would the first step be dealt with?

       2                     2
    /     \                /  \
   3       4   or this?   3    4
  / \      /             / \   
 5   NULL 1             5   1

Would be this the same if the node was empty instead?

Answer 1

A heap of integers does not have NULL values. I suppose the NULL is an indication of the capacity of the heap, meaning it can only have one more value before being full.

Would be this the same if the node was empty instead?

As unusual as this representation is, the NULL cannot mean anything else than that the node is empty. If it is considered as data, then there is an inconsistency. The data type used for the values in a heap should be consistent, and comparable. So NULL is not an option for data.

When you insert a next value, the first empty slot should be used for it. And then it should be sifted to its correct position.

So from:

     2
    / \
   3   4
  / \     
 5   NULL

to

     2
    / \
   3   4
  / \
 5   1

to

     1
    / \
   2   4
  / \     
 5   3

BTW: a "sorted heap" is not a thing. True, a sorted list is also a heap, but the power of the heap is that it does not need to always be sorted. It only guarantees the heap property, i.e. that a parent node is never greater than either of its children.