Heap (data structure): Difference between revisions

Revision as of 06:09, 18 November 2021

Revision as of 17:57, 20 November 2021

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:

* '''Insertion:''' Add the new element at the end of the heap, in the first available free space. ThisIf this will violate the heap property, sosift up the elementsnew are shifted upelement (or ''swim'' operation) until the heap property has been reestablished.

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

Thus* replacing'''Replacement:''' is done by deletingRemove the root and puttingput the ''new'' element in the root and siftingsift down,. avoiding a sifting up stepWhen compared to popextraction (siftfollowed downby ofinsertion, lastthis element)avoids followeda by push (sift up of new element)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''₂(''N'') − ''e''₂(''N'') (for a binary heap), where ''s''₂(''N'') is the sum of all digits of the binary representation of ''N'' and ''e''₂(''N'') is the exponent of 2 in the prime factorization of ''N''.<ref>{{citation