Heap (data structure): Difference between revisions

Revision as of 02:18, 5 November 2021

Revision as of 06:09, 18 November 2021

Line 41:

* The parent / child relationship is [[implicit data structure|defined implicitly]] by the elements' indices in the array.

[[File:Heap-as-array.svg|thumb|upright=1.25|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 '''{{mvar|i'''}}, its children are at indices '''{{tmath|2i + 1'''}} and '''{{tmath|2i + 2'''}}, and its parent is at index {{math|⌊(i−1''i''−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.

Line 48:

After an element is inserted into or deleted from a heap, the heap property may be violated, and the heap must be re-balanced by swapping elements within the array.

Although different type of heaps implement the operations differently, but the most common way is as follows: <br />

* '''Insertion:''' Add the new element at the end of the heap, in the first available free space. This will violate the heap property, so the elements are shifted up (or ''swim'' operation) until the heap property has been reestablished. <br />

* '''Extraction:''' Remove the root and insert the last element of the heap in the root and this will violate the heap property, so, sift down to reestablish the heap property (or ''sink'' operation).

Thus replacing is done by deleting the root and putting the ''new'' element in the root and sifting down, avoiding a sifting up step compared to pop (sift down of last element) followed by push (sift up of new element).