The heap insertion algorithm inserts a new value into a heap, maintaining the heap property. Let be a heap, storing elements over which the relation imposes a total ordering. Insertion of a value consists of initially adding to the bottom of the tree, and then sifting it upwards until the heap property is regained.

Sifting consists of comparing to its parent . If holds, then the heap property is violated. If this is the case, and are swapped and the operation is repeated for the new parent of .

Since is a balanced binary tree, it has a maximum depth of . Since the maximum number of times that the sift operation can occur is constrained by the depth of the tree, the worst case time complexity for heap insertion is . This means that a heap can be built from scratch to hold a multiset of values in time.

What follows is the pseudocode for implementing a heap insertion. For the given pseudocode, we presume that the heap is actually represented implicitly in an array (see the binary tree entry for details).