请输入您要查询的字词:

 

单词 HeapInsertionAlgorithm
释义

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

随便看

 

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

 

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