Min-Max-Heap

Min-Max-Heap

Ein Min-Max-Heap ist in der Informatik eine Baum-Datenstruktur

Die Min-Max-Heaps sind von Binären Heaps abgeleitet und werden eingesetzt um zweiendige Vorrangwarteschlangen effizient zu implementieren. Hierbei können sowohl das kleinste (findMin) als auch das größte (findMax) Element in konstanter Zeit gefunden werden. Die Neustrukturierung des Baumes nach dem Entfernen (extractMin bzw. extractMax) oder Einfügen (insert) von Elementen ist in logarithmischer Zeit möglich.

Min-Max-Heaps unterscheiden sich von Min-Heaps oder Max-Heaps: Die Knoten des Min-Max-Heaps sind nach dem sogenannten min-max-Prinzip angeordnet. Der Baum wird dabei in gerade und ungerade Ebenen unterteilt. In den geraden Ebenen befinden sich Knoten, die kleiner als alle ihrer Kindknoten sind. Entsprechend befinden sich in den ungeraden Ebenen ausschließlich Knoten, deren Kindknoten kleiner als sie selbst sind. In der Wurzel (in Ebene 0) befindet sich somit das kleinste Element des gesamten Heaps. Das größte Element ist im rechten oder linken Kindknoten der Wurzel zu finden.

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Min-max heap — A min max heap is a double ended priority queue implemented as a modified version of a binary heap. Like a binary heap, a min max heap is represented as a complete binary tree. Unlike a binary heap, though, the nodes in this tree do not obey the… …   Wikipedia

  • Max-Heap — In der Informatik ist ein Heap (wörtlich Haufen oder Halde) eine zumeist auf Bäumen basierende abstrakte Datenstruktur. In einem Heap können Objekte oder Elemente abgelegt und aus diesem wieder entnommen werden. Sie dienen damit der Speicherung… …   Deutsch Wikipedia

  • Min-Heap — In der Informatik ist ein Heap (wörtlich Haufen oder Halde) eine zumeist auf Bäumen basierende abstrakte Datenstruktur. In einem Heap können Objekte oder Elemente abgelegt und aus diesem wieder entnommen werden. Sie dienen damit der Speicherung… …   Deutsch Wikipedia

  • Heap (Datenstruktur) — In der Informatik ist ein Heap (wörtlich Haufen oder Halde) eine zumeist auf Bäumen basierende abstrakte Datenstruktur. In einem Heap können Objekte oder Elemente abgelegt und aus diesem wieder entnommen werden. Sie dienen damit der Speicherung… …   Deutsch Wikipedia

  • Heap-Sort — Der Heapsort Algorithmus beim Sortieren eines Arrays aus permutierten Werten. Der Algorithmus besteht aus zwei Schritten; im vorbereitenden Schritt wird das Array zu einem binären Heap umgeordnet, dessen Baumstruktur vor dem eigentlichen… …   Deutsch Wikipedia

  • Heap Sort — Der Heapsort Algorithmus beim Sortieren eines Arrays aus permutierten Werten. Der Algorithmus besteht aus zwei Schritten; im vorbereitenden Schritt wird das Array zu einem binären Heap umgeordnet, dessen Baumstruktur vor dem eigentlichen… …   Deutsch Wikipedia

  • Heap (data structure) — This article is about the programming data structure. For the dynamic memory area, see Dynamic memory allocation. Example of a complete binary max heap In computer science, a heap is a specialized tree based data structure that satisfies the heap …   Wikipedia

  • Binary heap — Example of a complete binary max heap Example of a complete binary min heap A binary …   Wikipedia

  • d-ary heap — The d ary heap or d heap is a priority queue data structure, a generalization of the binary heap in which the nodes have d children instead of 2.[1][2][3] Thus, a binary heap is a 2 heap. According to Tarjan[2] and Jensen et al …   Wikipedia

  • Binärer Heap — Binärer Min Heap 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… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”