Binary heap: Difference between revisions

Revision as of 04:30, 27 May 2025

Latest revision as of 15:54, 8 August 2025

(2 intermediate revisions by 2 users 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 32 ⟶ 34:

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