| dbo:abstract
|
- Els Monticles binaris (Binary Heaps en anglès) són un cas particular i senzill de l'estructura de dades Monticle, i estan basats en un arbre binari balancejat, que es pot veure com un arbre binari amb dues restriccions addicionals: Propietat de monticleCada node conté un valor superior al dels seus fills (per a un monticle per màxims) o més petit que el dels seus fills (per a un monticle per mínims).Arbre semicompletL'arbre està balancejat i en un mateix nivell les insercions es realitzen d'esquerra a dreta. Els monticles per màxims s'utilitzen freqüentment per representar cues de prioritat. A continuació es mostren dos monticles un per mínims i altre per màxims que representen el mateixes valors. 1 11/ \ / \2 3 9 10/ \ / \ / \ / \4 5 6 7 5 6 7 8/ \ / \ / \ / \8 9 10 11 1 2 3 4 L'ordre dels nodes germans en un monticle no està especificat en la propietat de monticle , de manera que els subarbre d'un node són intercanviables. (ca)
- Binární halda je obzvláště jednoduchý typ datové struktury halda, která je vytvořená použitím binárního stromu. Můžeme si jej představit jako binární strom se dvěma dalšími omezeními.
* Vlastnost tvaru – strom je buď perfektně vyvážený binární strom (všechny listy jsou ve stejné úrovni), nebo pokud je poslední úroveň stromu nekompletní, uzly plní strom zleva doprava.
* Vlastnost haldy - každý uzel je větší nebo roven všem svým potomkům „Větší než“ je chápáno ve smyslu porovnávací funkce zvolené k uspořádání haldy, nemusí se nutně jednat o „větší než“ v matematickém významu (nejedná se vždy o číselné hodnoty). Haldy, kde porovnávací funkcí je matematické „větší než“, jsou zvané max-haldy. Tam kde porovnávací funkcí je matematické „menší než“, jedná se o min-haldu. Častější jsou min-haldy, které lze jednoduše použít v prioritních frontách. Všimněte si, že pořadí sourozenců v haldě není v jejích vlastnostech určeno. Dva potomky téhož rodiče lze volně vyměnit (pokud to neporušuje vlastnosti haldy, porovnejte s binárním vyhledávacím stromem). (cs)
- A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues. The binary heap was introduced by J. W. J. Williams in 1964, as a data structure for heapsort. A binary heap is defined as a binary tree with two additional constraints:
* Shape property: a binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
* Heap property: the key stored in each node is either greater than or equal to (≥) or less than or equal to (≤) the keys in the node's children, according to some total order. Heaps where the parent key is greater than or equal to (≥) the child keys are called max-heaps; those where it is less than or equal to (≤) are called min-heaps. Efficient (logarithmic time) algorithms are known for the two operations needed to implement a priority queue on a binary heap: inserting an element, and removing the smallest or largest element from a min-heap or max-heap, respectively. Binary heaps are also commonly employed in the heapsort sorting algorithm, which is an in-place algorithm because binary heaps can be implemented as an implicit data structure, storing keys in an array and using their relative positions within that array to represent child–parent relationships. (en)
- Ein Binärer Heap ist eine Datenstruktur aus der Informatik zum effizienten Sortieren von Elementen. Das asymptotisch optimale Sortierverfahren Heapsort verwendet als zentrale Datenstruktur einen binären Heap. Des Weiteren wird der binäre Heap zur Implementierung einer Vorrangwarteschlange, in der das Element mit der höchsten Priorität effizient abgefragt und entfernt werden kann, verwendet.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-Relation (<) über den ganzen Zahlen darstellt. In der Literatur wird oft der Zusatz binär weggelassen, so dass je nach Zusammenhang der Heap als archetypische (binäre) Heap-Struktur (implementiert in einem Array) oder die Klasse aller Heap-Datenstrukturen gemeint ist.Des Weiteren wird bei Verwendung der Ordnungsrelation bzw. ein Heap als Min-Heap bzw. Max-Heap bezeichnet.Da sich die Operationen im Min- und Max-Heap nur durch die verwendete Ordnungsrelation unterscheiden, wird im Folgenden der binäre Heap und die Operationen darauf am Beispiel des Min-Heap definiert. (de)
- Los Montículos binarios (binary heaps en inglés) son un caso particular y sencillo de la estructura de datos Montículo, y está basada en un árbol binario balanceado, que puede verse como un árbol binario con dos restricciones adicionales: Propiedad de montículoCada nodo contiene un valor superior al de sus hijos (para un montículo por máximos) o más pequeño que el de sus hijos (para un montículo por mínimos).Árbol semicompletoEl árbol está balanceado y en un mismo nivel las inserciones se realizan de izquierda a derecha. Los montículos por máximos se utilizan frecuentemente para representar colas de prioridad. A continuación se muestran dos montículos: el primero por mínimos y el segundo por máximos, que representan el mismo conjunto de valores y además son semicompletos. 1 11 / \ / \ 2 3 9 10 / \ / \ / \ / \ 4 5 6 7 5 6 7 8 / \ / \ / \ / \ 8 9 10 11 1 2 3 4 El orden de los nodos hermanos en un montículo no está especificado en la propiedad de montículo, de manera que los subárboles de un nodo son intercambiables. (es)
- Uno heap binario, è uno heap sviluppato su un albero binario. È usato principalmente per la raccolta di collezioni di dati, dette dizionari, e per la rappresentazione di code di priorità. Lo heap binario deve sottostare alle seguenti condizioni:
* Condizione di heap: se A è un genitore di B, allora la chiave di A è ordinata rispetto alla chiave di B conformemente alla relazione d'ordine applicata all'intero heap. In parole più semplici, se il nodo A è genitore del nodo B, allora il nodo A ha maggior priorità di B. Uno heap binario può essere definito in modo che le chiavi più prioritarie siano quelle più piccole (si parla di heap a minimo) oppure in modo che le chiavi più prioritarie siano le più grandi (heap a massimo).
* Condizione di forma: tutti i livelli dello heap, tranne eventualmente l'ultimo, devono essere completi; se l'ultimo livello non è completo, i nodi devono essere disposti —per convenzione— a partire dall'estrema sinistra. (it)
- En informatique, un tas binaire est une structure de données utilisée notamment pour implémenter une file de priorité car elle permet de retirer l’élément de priorité maximale (resp. minimale) d'un ensemble ou d’insérer un élément dans l'ensemble en temps logarithmique tout en conservant la structure du tas binaire. On peut la représenter par un arbre binaire qui vérifie ces deux contraintes :
* C'est un arbre binaire parfait : tous les niveaux sauf le dernier doivent être totalement remplis et si le dernier ne l'est pas totalement, alors il doit être rempli de gauche à droite.
* C'est un tas : l'étiquette (qu'on appelle aussi clé ou key) de chaque nœud doit être supérieure ou égale (resp. inférieure ou égale) aux étiquettes de chacun de ses fils (la signification de supérieur ou égal dépend de la relation d'ordre choisie). Si la relation d'ordre choisie est "supérieure ou égale", on parle alors de tas-max (ou max-heap). Si la relation est "inférieure ou égale", on parle alors de tas-min (ou min-heap). (fr)
- 二分ヒープ（にぶんヒープ,バイナリヒープ,Binary heap）とは、二分木を使って作られるヒープ(データ構造)の特に単純な種類のひとつである。それは、二分木に、以下の2つの制約を追加したものとみなせる。
* 要素間の順序関係に従った比較によって、各々のノードはそのノードの子よりも大きいか等しくなるように配置される（heap property）
* 木は完全にバランスの取れた二分木（すべての葉は同じ高さにある）になるか、木のもっとも高い方がすべて埋まっていないならば、ノードは左から右へ順に埋まっていく（shape property） ここで「より大きい」とは、比較のためにいかなる比較関数を選択するかによって意味づけられる。ノード内のデータが常に数値であるとは限らないので、数量的な『より大きい』である必要はなく、数理的に言うところの全順序であればよい。 また、heap propertyのような制約を持つ木を一般に「部分順序付き木」と言う。ヒープは、部分順序付き二分木に、さらにshape propertyの制約を加えたものである。配列を使って実装できるという特性がある（後述）。 比較が数量的な「より大きい」であるヒープは最大ヒープ (max heap) と呼ばれる。また、比較が数量的な「より小さい」であるヒープは最小ヒープ (min heap) と呼ばれる。たとえば優先順位付き待ち行列において、小さい値が高い優先度を意味するのであれば、最小ヒープを使う。 ヒープ内の子同士の順序は、heap propertyによって特定できないことに注意すること。つまり、親を同じくする二つの子は、制約を壊さない限り自由に入れ替えることができる（Treapと比較せよ）。 (ja)
- 이진 힙(binary heap)이란 이진 트리를 이용하여 만든 힙 자료구조를 뜻한다. 또한 이진 힙은 완전 이진 트리이다. (ko)
- Kopiec binarny (ang. binary heap, czasem używa się też określenia sterta) – tablicowa struktura danych reprezentująca drzewo binarne, którego wszystkie poziomy z wyjątkiem ostatniego muszą być pełne. W przypadku, gdy ostatni poziom drzewa nie jest pełny, liście ułożone są od lewej do prawej strony drzewa. Wyróżniamy dwa rodzaje kopców binarnych: kopce binarne typu max w których wartość danego węzła niebędącego korzeniem jest zawsze mniejsza niż wartość jego rodzica oraz kopce binarne typu min w których wartość danego węzła niebędącego korzeniem jest zawsze większa niż wartość jego rodzica. (pl)
- Двои́чная ку́ча, пирами́да, или сортиру́ющее де́рево — такое двоичное дерево, для которого выполнены три условия: 1.
* Значение в любой вершине не меньше, чем значения её потомков. 2.
* Глубина всех листьев (расстояние до корня) отличается не более чем на 1 слой. 3.
* Последний слой заполняется слева направо без «дырок». Существуют также кучи, где значение в любой вершине, наоборот, не больше, чем значения её потомков. Такие кучи называются min-heap, а кучи, описанные выше — max-heap. В дальнейшем рассматриваются только max-heap. Все действия с min-heap осуществляются аналогично. Удобная структура данных для сортирующего дерева — массив A, у которого первый элемент, A[1] — элемент в корне, а потомками элемента A[i] являются A[2i] и A[2i+1] (при нумерации элементов с первого). При нумерации элементов с нулевого, корневой элемент — A[0], а потомки элемента A[i] — A[2i+1] и A[2i+2]. При таком способе хранения условия 2 и 3 выполнены автоматически. Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть , где N — количество узлов дерева. (ru)
- Двійкова купа (англ. binary heap) — це структура даних, що є масивом, який можна розглядати як майже повне двійкове дерево. Кожен вузол цього дерева відповідає певному елементу масива. На всіх рівнях, крім, можливо останнього, дерево повністю заповнене (заповнений рівень — такий, що містить максимально можливу кількість вузлів). Останній рівень заповнюється послідовно зліва направо до тих пір, доки в масиві не закінчаться елементи. Для масиву A у корені дерева знаходиться елемент A[1]. Далі дерево будується за наступним принципом: якщо якомусь вузлу відповідає індекс i, то індекс його батьківського вузла обчислюється за допомогою процедури Parent(i), індекс лівого дочірнього вузла — за допомогою процедури Left(i), а індекс правого дочірнього вузла — за допомогою процедури Right(i): Parent(i) return Left(i) return Right(i) return Розглядають два види бінарних куп: неспадні і незростаючі. В обох видах значення, що розташовані у вузлах купи, задовільняють властивості купи (англ. heap property).Властивісь незростаючої купи (англ. max-heap property) полягає в тому, що для кожного вузла крім кореневого виконується нерівність: . Іншими словами, значення вузла не перевищує значення батьківського вузла. Таким чином найбільший елемент знаходиться в корені дерева.Принцип побудови неспадної купи (англ. min-heap) протилежний. Властивість неспадної купи (англ. min-heap property) полягає в тому, що кожен елемент крім кореневого є неменшим за свій батьківський елемент: . (uk)
- 二叉堆（英語：binary heap）是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父節点的键值总是保持固定的序关系于任何一个子节点的键值，且每个節点的左子树和右子树都是一个二叉堆。 当父節点的键值总是大于或等于任何一个子节点的键值时为「最大堆」。当父節点的键值总是小于或等于任何一个子节点的键值时为「最小堆」。 (zh)
|
| rdfs:comment
|
- 이진 힙(binary heap)이란 이진 트리를 이용하여 만든 힙 자료구조를 뜻한다. 또한 이진 힙은 완전 이진 트리이다. (ko)
- Kopiec binarny (ang. binary heap, czasem używa się też określenia sterta) – tablicowa struktura danych reprezentująca drzewo binarne, którego wszystkie poziomy z wyjątkiem ostatniego muszą być pełne. W przypadku, gdy ostatni poziom drzewa nie jest pełny, liście ułożone są od lewej do prawej strony drzewa. Wyróżniamy dwa rodzaje kopców binarnych: kopce binarne typu max w których wartość danego węzła niebędącego korzeniem jest zawsze mniejsza niż wartość jego rodzica oraz kopce binarne typu min w których wartość danego węzła niebędącego korzeniem jest zawsze większa niż wartość jego rodzica. (pl)
- 二叉堆（英語：binary heap）是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父節点的键值总是保持固定的序关系于任何一个子节点的键值，且每个節点的左子树和右子树都是一个二叉堆。 当父節点的键值总是大于或等于任何一个子节点的键值时为「最大堆」。当父節点的键值总是小于或等于任何一个子节点的键值时为「最小堆」。 (zh)
- Els Monticles binaris (Binary Heaps en anglès) són un cas particular i senzill de l'estructura de dades Monticle, i estan basats en un arbre binari balancejat, que es pot veure com un arbre binari amb dues restriccions addicionals: Propietat de monticleCada node conté un valor superior al dels seus fills (per a un monticle per màxims) o més petit que el dels seus fills (per a un monticle per mínims).Arbre semicompletL'arbre està balancejat i en un mateix nivell les insercions es realitzen d'esquerra a dreta. 1 11/ \ / \2 3 9 10/ \ / \ / \ / \4 5 6 7 5 6 7 8/ \ / \ / \ / \8 9 10 11 1 2 3 4 (ca)
- Binární halda je obzvláště jednoduchý typ datové struktury halda, která je vytvořená použitím binárního stromu. Můžeme si jej představit jako binární strom se dvěma dalšími omezeními.
* Vlastnost tvaru – strom je buď perfektně vyvážený binární strom (všechny listy jsou ve stejné úrovni), nebo pokud je poslední úroveň stromu nekompletní, uzly plní strom zleva doprava.
* Vlastnost haldy - každý uzel je větší nebo roven všem svým potomkům (cs)
- A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues. The binary heap was introduced by J. W. J. Williams in 1964, as a data structure for heapsort. A binary heap is defined as a binary tree with two additional constraints: (en)
- Ein Binärer Heap ist eine Datenstruktur aus der Informatik zum effizienten Sortieren von Elementen. Das asymptotisch optimale Sortierverfahren Heapsort verwendet als zentrale Datenstruktur einen binären Heap. Des Weiteren wird der binäre Heap zur Implementierung einer Vorrangwarteschlange, in der das Element mit der höchsten Priorität effizient abgefragt und entfernt werden kann, verwendet.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-Relation (<) über den ganzen Zahlen darstellt. (de)
- Los Montículos binarios (binary heaps en inglés) son un caso particular y sencillo de la estructura de datos Montículo, y está basada en un árbol binario balanceado, que puede verse como un árbol binario con dos restricciones adicionales: Propiedad de montículoCada nodo contiene un valor superior al de sus hijos (para un montículo por máximos) o más pequeño que el de sus hijos (para un montículo por mínimos).Árbol semicompletoEl árbol está balanceado y en un mismo nivel las inserciones se realizan de izquierda a derecha. (es)
- Uno heap binario, è uno heap sviluppato su un albero binario. È usato principalmente per la raccolta di collezioni di dati, dette dizionari, e per la rappresentazione di code di priorità. Lo heap binario deve sottostare alle seguenti condizioni: (it)
- En informatique, un tas binaire est une structure de données utilisée notamment pour implémenter une file de priorité car elle permet de retirer l’élément de priorité maximale (resp. minimale) d'un ensemble ou d’insérer un élément dans l'ensemble en temps logarithmique tout en conservant la structure du tas binaire. On peut la représenter par un arbre binaire qui vérifie ces deux contraintes : Si la relation d'ordre choisie est "supérieure ou égale", on parle alors de tas-max (ou max-heap). Si la relation est "inférieure ou égale", on parle alors de tas-min (ou min-heap). (fr)
- 二分ヒープ（にぶんヒープ,バイナリヒープ,Binary heap）とは、二分木を使って作られるヒープ(データ構造)の特に単純な種類のひとつである。それは、二分木に、以下の2つの制約を追加したものとみなせる。
* 要素間の順序関係に従った比較によって、各々のノードはそのノードの子よりも大きいか等しくなるように配置される（heap property）
* 木は完全にバランスの取れた二分木（すべての葉は同じ高さにある）になるか、木のもっとも高い方がすべて埋まっていないならば、ノードは左から右へ順に埋まっていく（shape property） ここで「より大きい」とは、比較のためにいかなる比較関数を選択するかによって意味づけられる。ノード内のデータが常に数値であるとは限らないので、数量的な『より大きい』である必要はなく、数理的に言うところの全順序であればよい。 また、heap propertyのような制約を持つ木を一般に「部分順序付き木」と言う。ヒープは、部分順序付き二分木に、さらにshape propertyの制約を加えたものである。配列を使って実装できるという特性がある（後述）。 ヒープ内の子同士の順序は、heap propertyによって特定できないことに注意すること。つまり、親を同じくする二つの子は、制約を壊さない限り自由に入れ替えることができる（Treapと比較せよ）。 (ja)
- Двои́чная ку́ча, пирами́да, или сортиру́ющее де́рево — такое двоичное дерево, для которого выполнены три условия: 1.
* Значение в любой вершине не меньше, чем значения её потомков. 2.
* Глубина всех листьев (расстояние до корня) отличается не более чем на 1 слой. 3.
* Последний слой заполняется слева направо без «дырок». Существуют также кучи, где значение в любой вершине, наоборот, не больше, чем значения её потомков. Такие кучи называются min-heap, а кучи, описанные выше — max-heap. В дальнейшем рассматриваются только max-heap. Все действия с min-heap осуществляются аналогично. (ru)
- Двійкова купа (англ. binary heap) — це структура даних, що є масивом, який можна розглядати як майже повне двійкове дерево. Кожен вузол цього дерева відповідає певному елементу масива. На всіх рівнях, крім, можливо останнього, дерево повністю заповнене (заповнений рівень — такий, що містить максимально можливу кількість вузлів). Останній рівень заповнюється послідовно зліва направо до тих пір, доки в масиві не закінчаться елементи. Parent(i) return Left(i) return Right(i) return . . (uk)
|
