Binary Heap

A Binary Heap is a complete binary tree 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.

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