heap insertion algorithm
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 (http://planetmath.org/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).
- \\@startfield
\\@stopfield\\@addfield\\@startfieldInput: A heap (represented as an array) containing values and a new value to be inserted into .\\@stopfield\\@addfield\\@startfieldOutput: and , with inserted and the heap property preserved.\\@stopfield\\@addfield\\@startfieldProcedure:\\@stopfield\\@addfield\\@startfield\\@stopfield\\@addfield\\@startfield\\@stopfield\\@addfield\\@startfield\\@stopfield\\@addfield\\@startfield\\@stopfield\\@addfield\\@startfield\\=\\+\\@stopfield\\@addfield\\@startfield\\@stopfield\\@addfield\\@startfield\\=\\+\\@stopfield\\@addfield\\@startfield\\@stopfield\\@addfield\\@startfield\\=\\+\\@stopfield\\@addfield\\@startfield\\@stopfield\\@addfield\\@startfield\\@stopfield\\@addfield\\@startfield\\@stopfield\\@addfield\\@startfield\\@stopfield\\@addfield\\@startfield\\@stopfield\\@addfield\\@startfield\\@ifatmargin\\@ltab\\-\\@stopfield\\@addfield\\@startfield\\@ifatmargin\\@ltab\\-fi\\@stopfield\\@addfield\\@startfield\\@stopfield\\@addfield\\@startfield\\@stopfield\\@addfield\\@startfield\\@ifatmargin\\@ltab\\-od\\@stopfield\\@addfield\\@startfield\\@stopfield\\@addfield