Binary heap: Difference between revisions

Revision as of 10:42, 4 April 2024

Revision as of 15:59, 6 April 2024

Line 3:

|name=Binary (min) heap

|type=binary tree/heap

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

|

|invented_year=1964

<!-- NOTE:

Base of logarithms doesn't matter in big O notation. O(log n) is the same as O(lg n) or O(ln n) or O(log_2 n). A change of base is just a constant factor. So don't change these O(log n) complexities to O(lg n) or something else just to indicate a base-2 log. The base doesn't matter.

-->

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

|space_worst=O(n)

|search_avg=O(n)

|search_worst=O(n)

|insert_worst=O(log n)

|insert_avg=O(1)

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

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

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

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

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

|invented_year=1964

|find_min_avg=O(1)

|find_min_worst=O(1)}}

|merge_avg=O(n)

|merge_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]]