# Bottom Up Heapsort

# Bottom Up Heapsort

Bottom up heapsort improves the heapify operation used in heapsort. Instead of repeatedly comparing and swapping down the heap, it first follows a path to a leaf, then moves upward to place the element in its correct position.

This reduces the number of comparisons and improves performance while keeping the same asymptotic complexity.

## Problem

Given an array $A$ of length $n$, reorder it such that:

$$
A[0] \le A[1] \le \dots \le A[n-1]
$$

## Idea

Standard heapify performs comparisons at every level while moving down. Bottom up heapify separates the process into two phases:

1. follow the path of the larger child down to a leaf
2. move upward to find the correct position for the original element

This avoids unnecessary comparisons during downward movement.

## Algorithm

```text id="b4s2px"
bottom_up_heapsort(A):
    build_max_heap(A)

    for i from n - 1 down to 1:
        swap A[0] and A[i]
        bottom_up_heapify(A, 0, i)
```

Bottom up heapify:

```text id="t3n9kx"
bottom_up_heapify(A, root, size):
    x = A[root]
    i = root

    while left child exists:
        j = index of larger child
        move A[j] up to position i
        i = j

    while i > root and parent of i < x:
        move parent down
        i = parent index

    place x at position i
```

## Example

Let:

$$
A = [4, 10, 3, 5, 1]
$$

After building the heap:

$$
[10, 5, 3, 4, 1]
$$

During heapify after extraction, the algorithm first follows the path of larger children to the bottom, then inserts the original root value into the correct position along that path.

## Correctness

The downward phase ensures that a valid path in the heap is identified. The upward phase places the original value in the correct location along this path, maintaining the heap property. Since heapsort repeatedly extracts the maximum and restores the heap correctly, the final array is sorted.

## Complexity

| phase      | time          |
| ---------- | ------------- |
| build heap | $O(n)$        |
| extraction | $O(n \log n)$ |

Total:

$$
O(n \log n)
$$

The number of comparisons is reduced compared to standard heapify.

Space:

$$
O(1)
$$

## Properties

| property                  | value                        |
| ------------------------- | ---------------------------- |
| stable                    | no                           |
| in-place                  | yes                          |
| comparisons               | fewer than standard heapsort |
| implementation complexity | higher                       |

## Notes

Bottom up heapsort is mainly an optimization of the heapify step. It improves constant factors but does not change asymptotic complexity.

It is useful in performance critical environments where minimizing comparisons is important.

## Implementation

```python id="k8m2xp"
def bottom_up_heapsort(a):
    n = len(a)

    def heapify(root, size):
        x = a[root]
        i = root

        while 2 * i + 1 < size:
            j = 2 * i + 1
            if j + 1 < size and a[j + 1] > a[j]:
                j += 1
            a[i] = a[j]
            i = j

        while i > root:
            parent = (i - 1) // 2
            if a[parent] >= x:
                break
            a[i] = a[parent]
            i = parent

        a[i] = x

    for i in range(n // 2 - 1, -1, -1):
        heapify(i, n)

    for i in range(n - 1, 0, -1):
        a[0], a[i] = a[i], a[0]
        heapify(0, i)

    return a
```

```go id="z3p7nt"
func BottomUpHeapSort(a []int) {
	n := len(a)

	var heapify func(int, int)
	heapify = func(root, size int) {
		x := a[root]
		i := root

		for 2*i+1 < size {
			j := 2*i + 1
			if j+1 < size && a[j+1] > a[j] {
				j++
			}
			a[i] = a[j]
			i = j
		}

		for i > root {
			parent := (i - 1) / 2
			if a[parent] >= x {
				break
			}
			a[i] = a[parent]
			i = parent
		}

		a[i] = x
	}

	for i := n/2 - 1; i >= 0; i-- {
		heapify(i, n)
	}

	for i := n - 1; i > 0; i-- {
		a[0], a[i] = a[i], a[0]
		heapify(0, i)
	}
}
```