2.3 Node insertion

Let us assume the serial number of a heap is n. Then, when a new node is inserted, it is inserted as node n + 1. In general, this may break the requirement that the parent of a node must be greater than or equal to all children.

To make sure this rule is maintained, node n + 1 is compared with its parent, node (n + 1)∕k. If the nodes are out of order, then their values are exchanged. Then, we reapply the same technique to node (n + 1)∕k with its parent. This process is performed until a node is in order with its parent, or until we reach the root node.

The pseudocode to insert a node into a k-ary heap is specified in listing 1.


Listing 1:heapinsert
 
1define sub heap_insert 
2  by reference t : heap 
3  by value w : value_type 
4 
5  add new node n to t 
6  make v(n)= w 
7  while n is not root and v(n)>v(parent(n)) do 
8    swap v(n) with v(parent(v)) 
9    nparent(n
10  end while 
11end define sub

In the worst case, inserting a value into a heap is a Θ(log(n)) operation, where n is the number of items in the heap.