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 |
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.