heap insertion algorithm


The heap insertion algorithm inserts a new value into a heap, maintaining the heap property. Let H be a heap, storing n elements over which the relationMathworldPlanetmath (http://planetmath.org/Relation) imposes a total ordering. Insertion of a value x consists of initially adding x to the bottom of the tree, and then sifting it upwards until the heap property is regained.

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

Since H is a balanced binary tree, it has a maximum depth of log2n+1. 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 𝒪(logn). This means that a heap can be built from scratch to hold a multisetMathworldPlanetmath of n values in 𝒪(nlogn) 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

    HeapInsert(H,n,,x)\@stopfield\@addfield\@startfieldInput: A heap (H,) (represented as an array) containing n values and a new value x to be inserted into H.\@stopfield\@addfield\@startfieldOutput: H and n, with x inserted and the heap property preserved.\@stopfield\@addfield\@startfieldProcedure:\@stopfield\@addfield\@startfieldnn+1\@stopfield\@addfield\@startfieldH[n]x\@stopfield\@addfield\@startfieldchildn\@stopfield\@addfield\@startfieldparentn div 2\@stopfield\@addfield\@startfield𝗐𝗁𝗂𝗅𝖾\=\+parent1\@stopfield\@addfield\@startfield\@ifatmargin𝖽𝗈\@stopfield\@addfield\@startfield𝗂𝖿\=\+H[child]H[parent]\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield\@ifatmargin𝗍𝗁𝖾𝗇\=\+childparent\@stopfield\@addfield\@startfieldparentparent div 2\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield\@ifatmargin\@ifatmargin𝖾𝗅𝗌𝖾𝖾𝗅𝗌𝖾parent0\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield\@ifatmargin\@stopfield\@addfield\@startfield\@ifatmargin\@ltab\-\@stopfield\@addfield\@startfield\@ifatmargin\@ltab\-fi\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield\@ifatmargin\@stopfield\@addfield\@startfield\@ifatmargin\@ltab\-od\@stopfield\@addfield\@startfield\@stopfield\@addfield

Title heap insertion algorithm
Canonical name HeapInsertionAlgorithm
Date of creation 2013-03-22 12:29:27
Last modified on 2013-03-22 12:29:27
Owner mps (409)
Last modified by mps (409)
Numerical id 9
Author mps (409)
Entry type AlgorithmMathworldPlanetmath
Classification msc 68P20
Classification msc 68P10
Classification msc 68P05
Related topic Heap
Related topic HeapRemovalAlgorithm
Related topic HeapsortMathworldPlanetmath