请输入您要查询的字词:

 

单词 HeapRemovalAlgorithm
释义

heap removal algorithm


Definition

Let H be a heap storing n elements, and let be an operator that defines a total order over all of the values in H.If H is non-empty, then there is a value x in H such that xy holds for all values in H.The heap removal algorithm removes x from H and returns it,while maintaining the heap property of H.

The process of this algorithmMathworldPlanetmath is similar in nature to that of the heap insertion algorithm. First, if H only holds one value, then that value is x, which can simply be removed and returned.Otherwise, let z be the value stored in the right-most leaf of H.Since x is defined by the heap property to be the root of the tree,the value of x is saved, z is removed, and the value at the root of the tree is set to z. Then z 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 z is a leaf, the process ends. Otherwise, let a,b be the two children of z, chosen such that ab holds. If za holds, the process ends. Otherwise, a and z are swapped and the process repeats for z.

Analysis

Since H is a balanced binary tree, it has a maximum depth of log2n+1. Since the maximum number of times the sift operationMathworldPlanetmath can occur is constrained by the depth of the tree, the worst-case time complexity for heap insertion is 𝒪(logn).

Pseudocode

What follows is the pseudocode for implementing heap removal. For the givenpseudocode, we presume that the heap is actually represented implicitly inan array (see the binary tree entry for details), and that the heap contains at least one value.

  • \\@startfield

    HeapRemove(H,n,)\\@stopfield\\@addfield\\@startfieldInput. A heap (H,) (represented as an array) containing n>0 values.\\@stopfield\\@addfield\\@startfieldOutput. Removes and returns a value x from H such that xy holds for all y in H.\\@stopfield\\@addfield\\@startfieldProcedure:\\@stopfield\\@addfield\\@startfieldtopH[0]\\@stopfield\\@addfield\\@startfieldnn-1\\@stopfield\\@addfield\\@startfieldH[0]H[n]\\@stopfield\\@addfield\\@startfieldparent0\\@stopfield\\@addfield\\@startfieldchild1\\@stopfield\\@addfield\\@startfield𝗐𝗁𝗂𝗅𝖾\\=\\+child<n\\@stopfield\\@addfield\\@startfield\\@ifatmargin𝖽𝗈\\@stopfield\\@addfield\\@startfield𝗂𝖿\\=\\+child+1<n\\@stopfield\\@addfield\\@startfield\\@stopfield\\@addfield\\@startfield\\@ifatmargin𝗍𝗁𝖾𝗇\\=\\+\\@stopfield\\@addfield\\@startfield𝗂𝖿\\=\\+H[child+1]H[child]\\@stopfield\\@addfield\\@startfield\\@stopfield\\@addfield\\@startfield\\@ifatmargin𝗍𝗁𝖾𝗇\\=\\+\\@stopfield\\@addfield\\@startfieldchildchild+1\\@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\\-\\@stopfield\\@addfield\\@startfield\\@ifatmargin\\@ltab\\-fi\\@stopfield\\@addfield\\@startfield𝗂𝖿\\=\\+H[parent]H[child]\\@stopfield\\@addfield\\@startfield\\@stopfield\\@addfield\\@startfield\\@ifatmargin𝗍𝗁𝖾𝗇\\=\\+swap(H[parent],H[child])\\@stopfield\\@addfield\\@startfieldparentchild\\@stopfield\\@addfield\\@startfieldchild2child+1\\@stopfield\\@addfield\\@startfield\\@stopfield\\@addfield\\@startfield\\@ifatmargin\\@ifatmargin𝖾𝗅𝗌𝖾𝖾𝗅𝗌𝖾childn\\@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

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 9:17:30