heap removal algorithm
Definition
Let be a heap storing elements, and let be an operator that defines a total order over all of the values in . If is non-empty, then there is a value in such that holds for all values in . The heap removal algorithm removes from and returns it, while maintaining the heap property of .
The process of this algorithm is similar in nature to that of the heap insertion algorithm. First, if only holds one value, then that value is , which can simply be removed and returned. Otherwise, let be the value stored in the right-most leaf of . Since is defined by the heap property to be the root of the tree, the value of is saved, is removed, and the value at the root of the tree is set to . Then is sifted downwards into the tree until the heap property is regained.
The sifting process is similar to that of the heap insertion algorithm, only in reverse. First, if is a leaf, the process ends. Otherwise, let be the two children of , chosen such that holds. If holds, the process ends. Otherwise, and are swapped and the process repeats for .
Analysis
Since is a balanced binary tree, it has a maximum depth of . Since the maximum number of times the sift operation can occur is constrained by the depth of the tree, the worst-case time complexity for heap insertion is .
Pseudocode
What follows is the pseudocode for implementing heap removal. For the given pseudocode, we presume that the heap is actually represented implicitly in an array (see the binary tree entry for details), and that the heap contains at least one value.
-
\@startfield
\@stopfield\@addfield\@startfieldInput. A heap (represented as an array) containing values.\@stopfield\@addfield\@startfieldOutput. Removes and returns a value from such that holds for all in .\@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\@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\-\@stopfield\@addfield\@startfield\@ifatmargin\@ltab\-fi\@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
Title | heap removal algorithm |
---|---|
Canonical name | HeapRemovalAlgorithm |
Date of creation | 2013-03-22 12:29:30 |
Last modified on | 2013-03-22 12:29:30 |
Owner | mps (409) |
Last modified by | mps (409) |
Numerical id | 11 |
Author | mps (409) |
Entry type | Algorithm |
Classification | msc 68P20 |
Classification | msc 68P10 |
Classification | msc 68P05 |
Related topic | Heap |
Related topic | HeapInsertionAlgorithm |
Related topic | Heapsort |