Binary heap: Difference between revisions

Revision as of 22:13, 28 May 2025

Revision as of 11:33, 29 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 implementations(that ofis, [[logarithmic time]]) algorithms are known for 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.