In computer science, a binomial heap is a heap similar to a binary heap but also supports quickly merging two heaps. This is achieved by using a special tree structure. It is important as an implementation of the mergeable heap abstract data type (also called meldable heap), which is a priority queue supporting merge operation.
| Property | Value |
|---|
| dbpedia-owl:abstract
|
- In der Informatik ist ein Binomial-Heap eine Datenstruktur, genauer ein Heap, der sich, ähnlich wie binäre Heaps, als Vorrangwarteschlange einsetzen lässt. Das heißt, dass in beliebiger Reihenfolge effizient Elemente mit festgelegter Priorität in den Heap hineingelegt werden können und stets das Element mit höchster Priorität entnommen werden kann. Im Unterschied zu binären Heaps können Binomial-Heaps auch effizient vereinigt werden. Dies ermöglicht es beispielsweise, effizient in einem Mehrprozessor-Multitasking-System die Aufgaben eines überlasteten Prozessors einem anderen zu übertragen. Die Priorität der Elemente wird diesen durch Schlüssel aufgeprägt. Über der Menge der Schlüssel muss daher eine totale Ordnung bestehen, wie sie zum Beispiel die Kleiner-Gleich-Relation (≤) über den ganzen Zahlen darstellt. Binomial-Heaps wurden erstmals 1978 von Jean Vuillemin beschrieben. 1987 wurde von Michael L. Fredman und Robert Tarjan daraus eine neue Datenstruktur abgeleitet, die sogenannten Fibonacci-Heaps. Diese besitzen amortisiert teilweise bessere Laufzeiten und finden unter anderem Anwendung im Algorithmus von Dijkstra und im Algorithmus von Prim. Ihre Worst-Case Laufzeit ist teilweise aber deutlich schlechter, weshalb sie sich nicht für Online-Algorithmen eignen.
- In computer science, a binomial heap is a heap similar to a binary heap but also supports quickly merging two heaps. This is achieved by using a special tree structure. It is important as an implementation of the mergeable heap abstract data type (also called meldable heap), which is a priority queue supporting merge operation.
- Un heap binomiale è un insieme di alberi binomiali che soddisfa le seguenti proprietà: per qualsiasi intero (può anche non esserci). Ciò significa anche che non possono esservi più di un albero binomiale con il medesimo grado, ogni albero binomiale gode della proprietà di ordinamento parziale degli heap, ossia ogni nodo di ciascun albero è tale che la propria chiave sia sempre maggiore o uguale della chiave del nodo padre. Gli heap binomiali appartengono alla classe di strutture dati definite come heap aggregabili ossia strutture dati di tipo heap che oltre alle consuete procedure di ricerca della chiave minima, inserimento di un nodo, estrazione del nodo con chiave minima ed eliminazione di una chiave (operazioni implementate ad esempio negli heap binari, consentono anche l'implementazione dell'operazione di unione fra due heap che, a partire da due heap iniziali, restituisce un unico heap il cui insieme delle chiavi è pari all'unione degli insiemi delle chiavi dei due heap di partenza.
- 二項ヒープ（にこうヒープ、binomial heap）とは、計算機科学におけるデータ構造（ヒープ）の1つである。特徴は以下の通り。 二分ヒープとよく似たデータ構造であるが、二項ヒープは2つのヒープを素早くマージする操作をサポートしている。 特殊な木構造を用いることで実現される。 マージ可能な抽象データ型ヒープ（meldableヒープとも呼ばれる）の実装として重要。
- Kopiec dwumianowy - struktura danych umożliwiająca łatwe wykonywanie zwykłych operacji kopcowych (insert, findmin, deletemin) oraz operacji łączenia kopców (meld). Jest to zbiór drzew dwumianowych, które pamiętają elementy z uporządkowanego uniwersum w porządku kopcowym.
- Биномиальная куча — структура данных, реализующая абстрактный тип данных «Очередь с приоритетом», которая представляет собой набор биномиальных деревьев с двумя свойствами: ключ каждой вершины не меньше ключа ее родителя; все биномиальные деревья имеют разный размер. Из этих свойств вытекают два следствия. Во-первых, корень каждого из деревьев имеет наименьший ключ среди его вершин. Во-вторых, суммарное количество вершин в биномиальной куче однозначно определяет размеры входящих в него деревьев. Например, биномиальная куча с вершинами состоит из трёх деревьев высотой 3, 2 и 0 (см. рис. ) Следующие операции выполняются за время, где n — число вершин: Вставка нового элемента Нахождение элемента с минимальным ключом Удаление элемента с минимальным ключом Уменьшение значения ключа данного элемента Удаление данного элемента Объединение двух куч. Таким образом, биномиальная куча является сливаемой кучей, т. е кроме стандартных операций очереди с приоритетом (добавления, удаления, извлечения минимума, изменения ключей) предоставляет дополнительную операцию слияния двух куч.
- 在计算机科学中，二项堆（Template:Lang）是一种类似于二叉堆的堆结构。与二叉堆相比，其优势是可以快速合并两个堆，因此它属于可合并堆（Template:Lang）抽象数据类型的一种。
- En informatique, un tas binomial est une structure de données assez proche du tas binaire, mais qui permet aussi de fusionner deux tas rapidement. Ainsi, il supporte les opérations suivantes, toutes en O(ln n): Insérer un nouvel élément au tas Trouver l'élément de plus petite clé Effacer du tas l'élément de plus petite clé Diminuer la clé d'un élément donné Effacer un élément donné du tas Fusionner deux tas en un seul Le tas binomial est donc une implémentation du type abstrait tas fusionnable, ie une file à priorités permettant des opérations de fusion.
|
| dbpedia-owl:thumbnail
| |
| dbpedia-owl:wikiPageExternalLink
| |
| dcterms:subject
| |
| rdfs:comment
|
- In computer science, a binomial heap is a heap similar to a binary heap but also supports quickly merging two heaps. This is achieved by using a special tree structure. It is important as an implementation of the mergeable heap abstract data type (also called meldable heap), which is a priority queue supporting merge operation.
- 二項ヒープ（にこうヒープ、binomial heap）とは、計算機科学におけるデータ構造（ヒープ）の1つである。特徴は以下の通り。 二分ヒープとよく似たデータ構造であるが、二項ヒープは2つのヒープを素早くマージする操作をサポートしている。 特殊な木構造を用いることで実現される。 マージ可能な抽象データ型ヒープ（meldableヒープとも呼ばれる）の実装として重要。
- Kopiec dwumianowy - struktura danych umożliwiająca łatwe wykonywanie zwykłych operacji kopcowych (insert, findmin, deletemin) oraz operacji łączenia kopców (meld). Jest to zbiór drzew dwumianowych, które pamiętają elementy z uporządkowanego uniwersum w porządku kopcowym.
- 在计算机科学中，二项堆（Template:Lang）是一种类似于二叉堆的堆结构。与二叉堆相比，其优势是可以快速合并两个堆，因此它属于可合并堆（Template:Lang）抽象数据类型的一种。
- In der Informatik ist ein Binomial-Heap eine Datenstruktur, genauer ein Heap, der sich, ähnlich wie binäre Heaps, als Vorrangwarteschlange einsetzen lässt. Das heißt, dass in beliebiger Reihenfolge effizient Elemente mit festgelegter Priorität in den Heap hineingelegt werden können und stets das Element mit höchster Priorität entnommen werden kann. Im Unterschied zu binären Heaps können Binomial-Heaps auch effizient vereinigt werden.
- Un heap binomiale è un insieme di alberi binomiali che soddisfa le seguenti proprietà: per qualsiasi intero (può anche non esserci). Ciò significa anche che non possono esservi più di un albero binomiale con il medesimo grado, ogni albero binomiale gode della proprietà di ordinamento parziale degli heap, ossia ogni nodo di ciascun albero è tale che la propria chiave sia sempre maggiore o uguale della chiave del nodo padre.
- Биномиальная куча — структура данных, реализующая абстрактный тип данных «Очередь с приоритетом», которая представляет собой набор биномиальных деревьев с двумя свойствами: ключ каждой вершины не меньше ключа ее родителя; все биномиальные деревья имеют разный размер. Из этих свойств вытекают два следствия. Во-первых, корень каждого из деревьев имеет наименьший ключ среди его вершин.
- En informatique, un tas binomial est une structure de données assez proche du tas binaire, mais qui permet aussi de fusionner deux tas rapidement.
|
| rdfs:label
|
- Binomial-Heap
- Binomial heap
- Tas binomial
- Heap binomiale
- 二項ヒープ
- Kopiec dwumianowy
- Биномиальная куча
- 二项堆
|
| owl:sameAs
| |
| foaf:depiction
| |
| foaf:page
| |
| is dbpedia-owl:wikiPageDisambiguates
of | |
| is dbpedia-owl:wikiPageRedirects
of | |
| is owl:sameAs
of | |
| is foaf:primaryTopic
of | |
