# 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 relation  (http://planetmath.org/Relation) $\preceq$ 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 $x\preceq y$ holds, then the heap property is violated. If this is the case, $x$ and $y$ are swapped and the operation  is repeated for the new parent of $x$.

Since $H$ is a balanced binary tree, it has a maximum depth of $\lceil\log_{2}n\rceil+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 $\mathcal{O}(\log n)$. This means that a heap can be built from scratch to hold a multiset  of $n$ values in $\mathcal{O}(n\log n)$ 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

$\mathrm{HeapInsert}(H,n,\preceq,x)$\@stopfield\@addfield\@startfieldInput: A heap $(H,\preceq)$ (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\@startfield$n\leftarrow n+1$\@stopfield\@addfield\@startfield$H[n]\leftarrow x$\@stopfield\@addfield\@startfield$child\leftarrow n$\@stopfield\@addfield\@startfield$parent\leftarrow n\textrm{ div }2$\@stopfield\@addfield\@startfield$\mbox{\rm\bf\sf while}\$\=\+$parent\geq 1$\@stopfield\@addfield\@startfield$\@ifatmargin\ \mbox{\rm\bf\sf do}\$\@stopfield\@addfield\@startfield$\mbox{\rm\bf\sf if}\$\=\+$H[child]\preceq H[parent]$\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield$\@ifatmargin\ \mbox{\rm\bf\sf then}\$\=\+$child\leftarrow parent$\@stopfield\@addfield\@startfield$parent\leftarrow parent\textrm{ div }2$\@stopfield\@addfield\@startfield\@stopfield\@addfield\@startfield$\@ifatmargin\ \@ifatmargin\hbox to 0.0pt{\mbox{\rm\bf\sf else}\ }$$\mbox{\rm\bf\sf else}\ parent\leftarrow 0$\@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 HeapInsertionAlgorithm 2013-03-22 12:29:27 2013-03-22 12:29:27 mps (409) mps (409) 9 mps (409) Algorithm  msc 68P20 msc 68P10 msc 68P05 Heap HeapRemovalAlgorithm Heapsort  