Heap (data Structure) - Implementation and Operations

Implementation and Operations

Heaps are usually implemented in an array, and do not require pointers between elements.

The operations commonly performed with a heap are:

• create-heap: create an empty heap
• (a variant) create-heap: create a heap out of given array of elements
• find-max or find-min: find the maximum item of a max-heap or a minimum item of a min-heap, respectively
• delete-max or delete-min: removing the root node of a max- or min-heap, respectively
• increase-key or decrease-key: updating a key within a max- or min-heap, respectively
• insert: adding a new key to the heap
• merge: joining two heaps to form a valid new heap containing all the elements of both.

Different types of heaps implement the operations in different ways, but notably, insertion is often done by adding the new element at the end of the heap in the first available free space. This will tend to violate the heap property, and so the elements are then reordered until the heap property has been reestablished. Construction of a binary (or d-ary) heap out of given array of elements may be preformed faster than a sequence of consecutive insertions into originally empty heap using the classic Floyd's algorithm, with the worst-case number of comparisons equal to 2N − 2s₂(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.