Binary Heap

A Binary Heap is a complete binary tree (typically stored in an array), where each node satisfies the heap property: in a max-heap, parents are greater than or equal to their children, while in a min-heap, they are less than or equal. Heap Sort utilizes this structure by building a max-heap and repeatedly extracting the root element to the end of the array, resulting in an efficient O(n log n) sorting algorithm. Beyond sorting, heaps are widely used to implement priority queues.

How it Works

• Insertion: The new element is added to the end of the heap and then "bubbled up" (heapify-up) by repeatedly swapping it with its parent until the heap property is restored.
• Extraction: The root element is removed and replaced by the last element in the heap. This element is then "bubbled down" (heapify-down) by swapping it with its children until the heap property is satisfied.

Pseudocode

function insert(value):

    arr[n] = value

    i = n, n = n + 1

    while i > 0:

        parent = (i - 1) / 2

        if arr[parent] >= arr[i]:

            break

        swap(parent, i)

        i = parent

function extract():

    if n == 0: return null

    max = arr[0]

    arr[0] = arr[n - 1]

    n = n - 1

    heapify(0)

    return max