Binary heap: Difference between revisions

Revision as of 16:19, 29 August 2024

Revision as of 17:08, 1 September 2024

Line 226:

By swapping the values ''a''[''i''] and ''a''[''j''] the heap property for position ''i'' is established.

At this point, the only problem is that the heap property might not hold for index ''j''.

The shiftsift-down function is applied [[tail recursion|tail-recursively]] to index ''j'' until the heap property is established for all elements.

The shiftsift-down function is fast. In each step it only needs two comparisons and one swap. The index value where it is working doubles in each iteration, so that at most log₂ ''e'' steps are required.

For big heaps and using [[virtual memory]], storing elements in an array according to the above scheme is inefficient: (almost) every level is in a different [[Page (computer memory)|page]]. [[B-heap]]s are binary heaps that keep subtrees in a single page, reducing the number of pages accessed by up to a factor of ten.<ref>{{cite magazine|first = Poul-Henning|last= Kamp|url = http://queue.acm.org/detail.cfm?id=1814327 |title = You're Doing It Wrong|magazine= ACM Queue|date = June 11, 2010|volume = 8|issue = 6}}