The insert operation is conceptually very simple. Elements are inserted into the buffer until it is filled, and thereafter the buffer is inserted in the last node of the heap and sifted up until the heap condition holds. Anyway there is the possibility for a nasty implementation error here.- Consider the situation where the S largest elements of the heap are in the insertion buffer (size S). Now it is inserted in the last node of the heap. Assume then that the root page is full, i.e. it contains S elements, and that a node along the path to the root only has S/2 elements.- Now, for the siftup to be correct the net-result of the siftup should be that all the inserted elements are propagated to the root. But since siftup is not allowed to change the number of elements in a node this can not happen. Only S/2 elements can get past the half full node.
This possible bug is very nasty because it is extremely unlikely that it will be discovered by even the most intensive testing.
The description in [6] does not consider solutions to this problem and indeed I believe that the implementation is faulty, so I will leave it as an exercise for the reader to come up with a good solution. (Note. This error has been corrected in a later version of the paper.)
It should be noted that this is not a problem if the heap is used for sorting. Inserts can be completely avoided when sorting, and even if inserts are used, they are only used in a completely full heap.
The motivation for the requirement that the number of elements in the nodes must not change during a siftup, is that if the load factor of a node is increased, the smallest element of the node may become smaller, thereby possibly violating the heap property.