| dbo:abstract
|
- Heap Binomial (es)
- Binomiální halda je druh haldy, tedy datové struktury, která reprezentuje množinu čísel. Má podobné vlastnosti, jako binární halda, umí však navíc rychlé spojení dvou binomiálních hald. Binomiální haldy se používají zejména v aplikacích, kde je potřeba provádět rychle operace MIN a MERGE. Učebnicovým příkladem je například Dijkstrův algoritmus. Pro zajištění rychlé operace DECREASEKEY (tedy zmenšení prvku reprezentovaného nějakým uzlem) se pak používají Fibonacciho haldy. (cs)
- تعرف الكومة ذات الحدين في علوم الحاسوب بأنها كومة شبيهة بالكومة الثنائية إلا أنها تدعم إمكانية دمج كومتين مختلفتين مع بعضهما بشكل فعال، ويتم القيام بذلك عبر استخدام بنية معطيات شجرية خاصة. تعتبر الكومة ذات الحدين تحقيقاً هاماً لبنية المعطيات المجردة المسماة بالكومة القابلة للدمج، والتي تعرف بأنها رتلاً أفضلياً يدعم ميزة الدمج. (ar)
- In computer science, a binomial heap is a data structure that acts as a priority queue but also allows pairs of heaps to be merged.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. It is implemented as a heap similar to a binary heap but using a special tree structure that is different from the complete binary trees used by binary heaps. Binomial heaps were invented in 1978 by Jean Vuillemin. (en)
- 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 beschrieben. 1987 wurde von 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. (de)
- 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(log 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. (fr)
- 二項ヒープ（にこうヒープ、binomial heap）とは、計算機科学におけるデータ構造（ヒープ）の1つである。特徴は以下の通り。
* 二分ヒープとよく似たデータ構造であるが、二項ヒープは2つのヒープを素早くマージする操作をサポートしている。
* 特殊な木構造を用いることで実現される。
* マージ可能な抽象データ型ヒープ（meldableヒープとも呼ばれる）の実装として重要。 (ja)
- Un heap binomiale è un insieme di alberi binomiali che soddisfa le seguenti proprietà: 1.
* per qualsiasi intero non negativo esiste al più un albero binomiale la cui radice ha grado (può anche non esserci). Ciò significa anche che non possono esservi più di un albero binomiale con il medesimo grado, 2.
* 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. (it)
- 이항 힙에 대해 설명한다. (ko)
- Биномиальная куча (англ. binomial heap) — структура данных, реализующая абстрактный тип данных «очередь с приоритетом», которая представляет собой набор с двумя свойствами:
* ключ каждой вершины не меньше ключа её родителя;
* все биномиальные деревья имеют разный размер.Из этих свойств вытекают два следствия. Во-первых, корень каждого из деревьев имеет наименьший ключ среди его вершин. Во-вторых, суммарное количество вершин в биномиальной куче однозначно определяет размеры входящих в неё деревьев. Например, биномиальная куча с вершинами состоит из трёх деревьев высотой 3, 2 и 0 и имеющих, соответственно, 8, 4 и 1 элементов (см. рис.) Следующие операции выполняются за время , где n — число вершин:
* Вставка нового элемента (амортизированное )
* Нахождение элемента с минимальным ключом
* Удаление элемента с минимальным ключом
* Уменьшение значения ключа данного элемента
* Удаление данного элемента
* Объединение двух куч. Таким образом, биномиальная куча является сливаемой кучей, то есть кроме стандартных операций очереди с приоритетом (добавления, удаления, извлечения минимума, изменения ключей) предоставляет дополнительную операцию слияния двух куч. (ru)
- Kopiec dwumianowy – struktura danych umożliwiająca łatwe wykonywanie zwykłych operacji kopcowych (insert, findmin, deletemin) oraz operacji łączenia kopców (meld). Jest to lista uporządkowanych (względem rzędu) drzew dwumianowych, które pamiętają elementy z uporządkowanego uniwersum w porządku kopcowym. (pl)
- Em ciência da computação, um heap binomial é um tipo de heap semelhante a um , mas que também suporta a rápida união entre duas heaps. Isso é conseguido através do uso de uma estrutura de árvore especial. Ela é importante como uma implementação da mergeable heap (tipo abstrato de dado), que é uma que suporta a operação de merge. (pt)
- Біноміальна купа (англ. binomial heap) — це множина біноміальних дерев, що задовольняє властивостям біноміальної купи: 1.
* Кожне біноміальне дерево у купі підпорядковується властивості неспадної купи (англ. min-heap property): ключ вузла не менший за ключ його батьківського вузла. 2.
* Для будь-якого невід'ємного цілого k в купі існує не більше одного біноміального дерева, чий корінь має ступінь k. З даних властивостей випливає, що біноміальна купа, що має n вузлів, складається з не більше ніж біноміальних дерев. Завдяки своїй структурі, біноміальне дерево ступеня k можна побудувати з двох дерев ступеня k−1 тривіальним приєднанням одного з них до іншого, як найлівішого підпорядкованого дерева. Ця властивість є центральною для операції злиття біноміальних дерев, яка становить їхню основну перевагу над звичайними купами. Ім'я походить від того факту, що біноміальне дерево ступеня має вузлів на глибині . (uk)
- 在计算机科学中，二项堆（binomial heap）是一种类似于二叉堆的堆结构。与二叉堆相比，其优势是可以快速合并两个堆，因此它属于可合并堆（mergeable heap）抽象数据类型的一种。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 13033 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Heap Binomial (es)
- Binomiální halda je druh haldy, tedy datové struktury, která reprezentuje množinu čísel. Má podobné vlastnosti, jako binární halda, umí však navíc rychlé spojení dvou binomiálních hald. Binomiální haldy se používají zejména v aplikacích, kde je potřeba provádět rychle operace MIN a MERGE. Učebnicovým příkladem je například Dijkstrův algoritmus. Pro zajištění rychlé operace DECREASEKEY (tedy zmenšení prvku reprezentovaného nějakým uzlem) se pak používají Fibonacciho haldy. (cs)
- تعرف الكومة ذات الحدين في علوم الحاسوب بأنها كومة شبيهة بالكومة الثنائية إلا أنها تدعم إمكانية دمج كومتين مختلفتين مع بعضهما بشكل فعال، ويتم القيام بذلك عبر استخدام بنية معطيات شجرية خاصة. تعتبر الكومة ذات الحدين تحقيقاً هاماً لبنية المعطيات المجردة المسماة بالكومة القابلة للدمج، والتي تعرف بأنها رتلاً أفضلياً يدعم ميزة الدمج. (ar)
- In computer science, a binomial heap is a data structure that acts as a priority queue but also allows pairs of heaps to be merged.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. It is implemented as a heap similar to a binary heap but using a special tree structure that is different from the complete binary trees used by binary heaps. Binomial heaps were invented in 1978 by Jean Vuillemin. (en)
- 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(log 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. (fr)
- 二項ヒープ（にこうヒープ、binomial heap）とは、計算機科学におけるデータ構造（ヒープ）の1つである。特徴は以下の通り。
* 二分ヒープとよく似たデータ構造であるが、二項ヒープは2つのヒープを素早くマージする操作をサポートしている。
* 特殊な木構造を用いることで実現される。
* マージ可能な抽象データ型ヒープ（meldableヒープとも呼ばれる）の実装として重要。 (ja)
- 이항 힙에 대해 설명한다. (ko)
- Kopiec dwumianowy – struktura danych umożliwiająca łatwe wykonywanie zwykłych operacji kopcowych (insert, findmin, deletemin) oraz operacji łączenia kopców (meld). Jest to lista uporządkowanych (względem rzędu) drzew dwumianowych, które pamiętają elementy z uporządkowanego uniwersum w porządku kopcowym. (pl)
- Em ciência da computação, um heap binomial é um tipo de heap semelhante a um , mas que também suporta a rápida união entre duas heaps. Isso é conseguido através do uso de uma estrutura de árvore especial. Ela é importante como uma implementação da mergeable heap (tipo abstrato de dado), que é uma que suporta a operação de merge. (pt)
- 在计算机科学中，二项堆（binomial heap）是一种类似于二叉堆的堆结构。与二叉堆相比，其优势是可以快速合并两个堆，因此它属于可合并堆（mergeable heap）抽象数据类型的一种。 (zh)
- 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. (de)
- Un heap binomiale è un insieme di alberi binomiali che soddisfa le seguenti proprietà: 1.
* per qualsiasi intero non negativo esiste al più un albero binomiale la cui radice ha grado (può anche non esserci). Ciò significa anche che non possono esservi più di un albero binomiale con il medesimo grado, 2.
* 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. (it)
- Биномиальная куча (англ. binomial heap) — структура данных, реализующая абстрактный тип данных «очередь с приоритетом», которая представляет собой набор с двумя свойствами:
* ключ каждой вершины не меньше ключа её родителя;
* все биномиальные деревья имеют разный размер.Из этих свойств вытекают два следствия. Во-первых, корень каждого из деревьев имеет наименьший ключ среди его вершин. Во-вторых, суммарное количество вершин в биномиальной куче однозначно определяет размеры входящих в неё деревьев. Например, биномиальная куча с вершинами состоит из трёх деревьев высотой 3, 2 и 0 и имеющих, соответственно, 8, 4 и 1 элементов (см. рис.) (ru)
- Біноміальна купа (англ. binomial heap) — це множина біноміальних дерев, що задовольняє властивостям біноміальної купи: 1.
* Кожне біноміальне дерево у купі підпорядковується властивості неспадної купи (англ. min-heap property): ключ вузла не менший за ключ його батьківського вузла. 2.
* Для будь-якого невід'ємного цілого k в купі існує не більше одного біноміального дерева, чий корінь має ступінь k. З даних властивостей випливає, що біноміальна купа, що має n вузлів, складається з не більше ніж біноміальних дерев. (uk)
|
| rdfs:label
|
- الكومة ذات الحدين (بنية معطيات) (ar)
- Binomiální halda (cs)
- Binomial-Heap (de)
- Heap Binomial (es)
- Binomial heap (en)
- Heap binomiale (it)
- Tas binomial (fr)
- 이항 힙 (ko)
- 二項ヒープ (ja)
- Kopiec dwumianowy (pl)
- Биномиальная куча (ru)
- Heap binomial (pt)
- Біноміальна купа (uk)
- 二项堆 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
