Min-max heap

A min-max heap is in computer science , a tree - data structure .

The min-max heaps are derived from binary heaps and are used to efficiently implement double-ended priority queues . Both the smallest (findMin) and the largest (findMax) element can be found in constant time . The restructuring of the tree after removing ( extractMin or extractMax ) or inserting (insert) elements is possible in logarithmic time.

Min-max heaps differ from min-heaps or max heaps : The nodes of the min-max heap are arranged according to the so-called min-max principle. The tree is divided into even and odd levels. In the even planes there are nodes that are smaller than all of their child nodes. Accordingly, there are only nodes in the odd levels whose child nodes are smaller than themselves. The smallest element of the entire heap is located in the root (in level 0). The largest element can be found in the right or left child node of the root.

literature

• MD Atkinson, J.-R. Sack, N. Santoro, T. Strothotte: Min-max Heaps and Generalized Priority Queues . In: Communications of the ACM . tape 29 , no. 10 , 1986, ISSN  0001-0782 , pp. 996-1000 , doi : 10.1145 / 6617.6621 .