Binary heap: Difference between revisions

Revision as of 22:13, 28 May 2025

Latest revision as of 15:54, 8 August 2025

(One intermediate revision by one other user not shown)

Line 1:

{{Short description|Variant of heap data structure}}

{{Infobox data structure

| name = Binary (min) heap

| type = binary tree/heap

| invented_by = [[J. W. J. Williams]]

| invented_year = 1964

<!-- NOTE:

For the purposes of "Big O" notation, all bases are equivalent, because changing the base of a log only introduces a constant factor.

Line 10:

DO: O(log n)

DON'T: O(lg n), O(log2 n), O(log_2 n), O(ln n), O(log10 n), etc.

-->| insert_worst = O(log ''n'')

-->

| insert_avg = O(1)

|insert_worst=O(log ''n'')

|decrease_key_worst delete_min_avg = O(log ''n'')

|insert_avg=O(1)

|delete_min_avg delete_min_worst = O(log ''n'')

|delete_min_worst decrease_key_avg = O(log ''n'')

|decrease_key_avg decrease_key_worst = O(log ''n'')

| find_min_avg = O(1)

|decrease_key_worst=O(log ''n'')

|find_min_avg find_min_worst = O(1)

| merge_avg = O(''n'')

|find_min_worst=O(1)

|merge_avg merge_worst = O(''n'')

|merge_worst space_avg = O(''n'')}}

| space_worst = O(n)

}}

[[File:Max-Heap.svg|thumb|right|Example of a complete binary max-heap]]

[[File:Min-heap.png|thumb|right|Example of a complete binary min heap]]

Line 29 ⟶ 31:

*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.