# Heap
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`.

```c
// 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.

| Operation | Time |
|---|---|
| Insert | O(log n) |
| Extract min/max | O(log n) |
| Peek min/max | O(1) |
| Build from array | O(n) |