A heap is a Binary tree stored in an Array that maintains the heap property: in a max-heap, every parent is greater than or equal to its children, so the maximum element is always at the root. In a min-heap the relationship is reversed and the minimum is at the root. The tree is complete (all levels filled except possibly the last, which fills left-to-right), which allows a compact array representation with no pointers.

For a node at index i (0-based), its left child is at 2i + 1, its right child at 2i + 2, and its parent at (i - 1) / 2.

// max-heap: bubble up after inserting at the end
void push(int *heap, int *n, int val) {
    int i = (*n)++;
    heap[i] = val;
    while (i > 0 && heap[(i-1)/2] < heap[i]) {
        int tmp = heap[i]; heap[i] = heap[(i-1)/2]; heap[(i-1)/2] = tmp;
        i = (i - 1) / 2;
    }
}

The main use is a priority queue: insert in O(log n) and always extract the highest-priority element in O(log n). Extracting the maximum removes the root, moves the last element to the root, then sifts down by repeatedly swapping with the larger child until the heap property is restored.

Heapsort builds a heap from an unsorted array in O(n) using repeated sift-down from the middle, then extracts the maximum n times to produce a sorted sequence. The result is an O(n log n) in-place sort with O(1) extra memory, though with worse cache behaviour than quicksort in practice.