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

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