| dbpedia-owl:abstract
|
- In der Informatik ist ein Binärer Heap eine Datenstruktur, genauer ein Heap, der sich als Vorrangwarteschlange einsetzen lässt, das heißt, es können in beliebiger Reihenfolge effizient Elemente mit festgelegter Priorität in den Heap hineingelegt und stets das Element mit höchster Priorität entnommen werden. 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. Man unterscheidet zwischen: Min-Heap: Der kleinste Schlüssel bildet die Wurzel des Baumes und alle Nachfolger sind größer. Max-Heap: Der größte Schlüssel bildet die Wurzel des Baumes und alle Nachfolger sind kleiner. Die beiden Strukturen und Operationen auf diesen Strukturen sind einander analog. Dieser Artikel beschränkt sich daher auf den Min-Heap.
- A binary heap is a heap data structure created using a binary tree. It can be seen as a binary tree with two additional constraints: The shape property: the tree 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. The heap property: each node is greater than or equal to each of its children according to a comparison predicate defined for the data structure. Heaps with a mathematical "greater than or equal to" comparison function are called max-heaps; those with a mathematical "less than or equal to" comparison function are called min-heaps. Min-heaps are often used to implement priority queues. Since the ordering of siblings in a heap is not specified by the heap property, a single node's two children can be freely interchanged unless doing so violates the shape property. The binary heap is a special case of the d-ary heap in which d = 2. It is possible to modify the heap structure to allow extraction of both the smallest and largest element in time. To do this, the rows alternate between min heap and max heap. The algorithms are roughly the same, but, in each step, one must consider the alternating rows with alternating comparisons. The performance is roughly the same as a normal single direction heap. This idea can be generalised to a min-max-median heap.
- 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ículo Cada 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 semicompleto El á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 uno por mínimos y otro por máximos que representan el mismo conjunto de valores. 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.
- ファイル:Max-heap. png 最大ヒープによる二分ヒープの例 二分ヒープ（にぶんヒープ,バイナリヒープ,Binary heap）とは、二分木を使って作られるヒープの特に単純な種類のひとつである。それは、二分木に2つの制約を追加したものとみなせる。 形特性 木は完全にバランスの取れた二分木（すべての葉は同じ高さにある）になるか、木のもっとも高い方がすべて埋まっていないならば、ノードは左から右へ順に埋まっていく。 ヒーププロパティ データ構造全体を決定するための比較述語にしたがって、各々のノードはそのノードの子よりも大きいか等しくなるように配置される。 「より大きい」とは、ヒープをソートするためにどの比較関数を選択するかによって意味づけられ、ノード内のデータが常に数値であるとは限らないので数学的感覚での『より大きい』必要はない。比較関数が数学的な「より大きい」であるヒープは最大ヒープ (max heap) と呼ばれる。また、比較関数が数学的な「より小さい」であるヒープは最小ヒープ (min heap) と呼ばれる。通常は、優先順位付き待ち行列にすぐに適用できることから、最小ヒープが使われる。 ヒープ内の子同士の順序は、ヒーププロパティによって特定できないことに注意すること。つまり、親を同じくする二つの子は、Treapと比較して形特性を壊さない限り自由に入れ替えることができる。
- Kopiec binarny (czasem używa się też określenia sterta) - kopiec stworzony jako drzewo binarne. Kopiec binarny musi być kopcem zupełnym, czyli liście występują na ostatnim i ewentualnie przedostatnim poziomie w drzewie (gdy ostatni poziom nie jest całkowicie wypełniony), liście na ostatnim poziomie są spójnie ułożone od strony lewej do prawej.
- 二叉堆是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值，且每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。 当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。
- Двои́чная ку́ча, пирами́да, или сортиру́ющее де́рево — такое двоичное дерево, для которого выполнены три условия: Значение в любой вершине не меньше, чем значения её потомков. Каждый лист имеет глубину (расстояние до корня) либо d либо d-1. Иными словами, если назвать слоем совокупность вершин, находящихся на определённой глубине, то все слои, кроме, быть может, последнего, заполнены полностью. Последний слой заполняется слева направо. Существуют также кучи, где значение в любой вершине, наоборот, не больше, чем значения её потомков. Такие кучи называются min-heap, а кучи, описанные выше — max-heap. В дальнейшем рассматриваются только max-heap. Все действия с min-heap осуществляются аналогично. Удобная структура данных для сортирующего дерева — массив A, у которого первый элемент, A[1 1] — элемент в корне, а потомками элемента A[i i] являются A[2i 2i] и A[2i+1 2i+1] (при нумерации элементов с первого). При нумерации элементов с нулевого, корневой элемент — A[0 0], а потомки элемента A[i i] — A[2i+1 2i+1] и A[2i+2 2i+2]. При таком способе хранения условия 2 и 3 выполнены автоматически. Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть, где N — количество узлов дерева.
|
| rdfs:comment
|
- Kopiec binarny (czasem używa się też określenia sterta) - kopiec stworzony jako drzewo binarne. Kopiec binarny musi być kopcem zupełnym, czyli liście występują na ostatnim i ewentualnie przedostatnim poziomie w drzewie (gdy ostatni poziom nie jest całkowicie wypełniony), liście na ostatnim poziomie są spójnie ułożone od strony lewej do prawej.
- 二叉堆是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值，且每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。 当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。
- In der Informatik ist ein Binärer Heap eine Datenstruktur, genauer ein Heap, der sich als Vorrangwarteschlange einsetzen lässt, das heißt, es können in beliebiger Reihenfolge effizient Elemente mit festgelegter Priorität in den Heap hineingelegt und stets das Element mit höchster Priorität entnommen werden. Die Priorität der Elemente wird diesen durch Schlüssel aufgeprägt.
- A binary heap is a heap data structure created using a binary tree. It can be seen as a binary tree with two additional constraints: The shape property: the tree 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.
- 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ículo Cada 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).
- ファイル:Max-heap.
- Двои́чная ку́ча, пирами́да, или сортиру́ющее де́рево — такое двоичное дерево, для которого выполнены три условия: Значение в любой вершине не меньше, чем значения её потомков. Каждый лист имеет глубину (расстояние до корня) либо d либо d-1. Иными словами, если назвать слоем совокупность вершин, находящихся на определённой глубине, то все слои, кроме, быть может, последнего, заполнены полностью. Последний слой заполняется слева направо.
|
