Binary heap: Difference between revisions

Revision as of 05:13, 20 May 2025

Latest revision as of 15:54, 8 August 2025

(4 intermediate revisions by 3 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==

Line 242 ⟶ 244:

The operation of merging two binary heaps takes Θ(''n'') for equal-sized heaps. The best you can do is (in case of array implementation) simply concatenating the two heap arrays and build a heap of the result.<ref>Chris L. Kuszmaul.

[http://nist.gov/dads/HTML/binaryheap.html "binary heap"] {{Webarchive| url=https://web.archive.org/web/20080808141408/http://www.nist.gov/dads/HTML/binaryheap.html |date=2008-08-08 }}.

Dictionary of Algorithms and Data Structures, Paul E. Black, ed., U.S. National Institute of Standards and Technology. 16 November 2009.</ref> A heap on ''n'' elements can be merged with a heap on ''k'' elements using O(log ''n'' log ''k'') key comparisons, or, in case of a pointer-based implementation, in O(log ''n'' log ''k'') time.<ref>[[Jörg-Rüdiger Sack|J.-R. Sack]] and T. Strothotte

[https://doi.org/10.1007%2FBF00264229 "An Algorithm for Merging Heaps"],

Acta Informatica 22, 171-186 (1985).</ref> An algorithm for splitting a heap on ''n'' elements into two heaps on ''k'' and ''n-k'' elements, respectively, based on a new view

of heaps as an ordered collections of subheaps was presented in.<ref>{{Cite journal |doi = 10.1016/0890-5401(90)90026-E|title = A characterization of heaps and its applications|journal = Information and Computation|volume = 86|pages = 69–86|year = 1990|last1 = Sack|first1 = Jörg-Rüdiger|author1-link = Jörg-Rüdiger Sack| last2 = Strothotte|first2 = Thomas|doi-access = free}}</ref> The algorithm requires O(log ''n'' * log ''n'') comparisons. The view also presents a new and conceptually simple algorithm for merging heaps. When merging is a common task, a different heap implementation is recommended, such as [[binomial heap]]s, which can be merged in O(log ''n'').

Additionally, a binary heap can be implemented with a traditional binary tree data structure, but there is an issue with finding the adjacent element on the last level on the binary heap when adding an element. This element can be determined algorithmically or by adding extra data to the nodes, called "threading" the tree—instead of merely storing references to the children, we store the [[inorder]] successor of the node as well.

Line 251 ⟶ 253:

It is possible to modify the heap structure to make the extraction of both the smallest and largest element possible in [[Big O notation|<math>O</math>]]<math>(\log n)</math> time.<ref name="sym">{{cite web

| url = http://cg.scs.carleton.ca/~morin/teaching/5408/refs/minmax.pdf

| authorauthor1 = Atkinson, M.D.

| author1-link = Michael D. Atkinson

| author2 = J.-R. Sack

| author2-link = Jörg-Rüdiger Sack