Binary heap: Difference between revisions

Revision as of 04:30, 27 May 2025

Revision as of 22:13, 28 May 2025

Line 29:

*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 (thatimplementations is, [[logarithmic time]]) algorithms are known forof the two operations needed to implement a priority queue on a binary heap. These can be implemented in [[Logarithmic time]]:

*Inserting an element;

*Removing the smallest or largest element from (respectively) a min-heap or max-heap.

Binary heaps are also commonly employed in the [[heapsort]] [[sorting algorithm]], which is an in-place algorithm becauseas 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.

==Heap operations==