Heap (data structure): Difference between revisions

Revision as of 04:30, 20 September 2021

Revision as of 15:03, 3 October 2021

Line 42:

[[File:Heap-as-array.svg|thumb|upright=1.2|Example of a complete binary max-heap with node keys being integers from 1 to 100 and how it would be stored in an array.]]

For a [[binary heap]], in the array, the first index contains the root element. The next two indices of the array contain the root's children. The next four indices contain the four children of the root's two child nodes, and so on. Therefore, given a node at index '''i''', its children are at indices '''2i + 1''' and '''2i + 2''', and its parent is at index '''{{math|⌊(i-1i−1)/2⌋}}'''. This simple indexing scheme makes it efficient to move "up" or "down" the tree.

Balancing a heap is done by sift-up or sift-down operations (swapping elements which are out of order). As we can build a heap from an array without requiring extra memory (for the nodes, for example), [[heapsort]] can be used to sort an array in-place.