Editing Heap (data structure) (section)

==Implementation using arrays==
Heaps are usually implemented with an [[array data structure|array]], as follows:

* Each element in the array represents a node of the heap, and
* 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.5|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)/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.

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 types of heaps implement the operations differently, the most common way is as follows:
* '''Insertion:''' Add the new element at the end of the heap, in the first available free space. If this will violate the heap property, sift up the new element (''swim'' operation) until the heap property has been reestablished.
* '''Extraction:''' Remove the root and insert the last element of the heap in the root. If this will violate the heap property, sift down the new root (''sink'' operation) to reestablish the heap property.
* '''Replacement:''' Remove the root and put the ''new'' element in the root and sift down. When compared to extraction followed by insertion, this avoids a sift up step.

Construction of a binary (or ''d''-ary) heap out of a given array of elements may be performed in linear time using the classic [[Heapsort#Variations|Floyd algorithm]], with the worst-case number of comparisons equal to 2''N'' − 2''s''<sub>2</sub>(''N'') − ''e''<sub>2</sub>(''N'') (for a binary heap), where ''s''<sub>2</sub>(''N'') is the sum of all digits of the binary representation of ''N'' and ''e''<sub>2</sub>(''N'') is the exponent of 2 in the prime factorization of ''N''.<ref>{{citation
 | last1 = Suchenek | first1 = Marek A.
 | title = Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program
 | doi = 10.3233/FI-2012-751
 | pages = 75–92
 | publisher = IOS Press
 | journal = Fundamenta Informaticae
 | volume = 120
 | issue = 1
 | year = 2012}}.</ref> This is faster than a sequence of consecutive insertions into an originally empty heap, which is log-linear.{{efn|Each insertion takes O(log(''k'')) in the existing size of the heap, thus <math>\sum_{k=1}^n O(\log k)</math>. Since <math>\log n/2 = (\log n) - 1</math>, a constant factor (half) of these insertions are within a constant factor of the maximum, so asymptotically we can assume <math>k = n</math>; formally the time is <math>n O(\log n) - O(n) = O(n \log n)</math>. This can also be readily seen from [[Stirling's approximation]].}}