# Ternary Heapsort

# Ternary Heapsort

Ternary heapsort replaces the binary heap with a ternary heap, where each node has up to three children instead of two. This reduces the height of the heap, which can reduce the number of levels traversed during heap operations.

The tradeoff is that each step may require more comparisons to select the largest child.

## Problem

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

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

## Idea

In a ternary heap, the children of node $i$ are:

$$
3i + 1,\quad 3i + 2,\quad 3i + 3
$$

This reduces the height of the heap to:

$$
O(\log_3 n)
$$

which is smaller than the binary heap height:

$$
O(\log_2 n)
$$

## Algorithm

```text id="t2k8xp"
ternary_heapsort(A):
    build_ternary_heap(A)

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

Heap construction:

```text id="p7s4qd"
build_ternary_heap(A):
    for i from floor((n - 2) / 3) down to 0:
        heapify(A, i, n)
```

Heapify:

```text id="v9m3ks"
heapify(A, i, size):
    largest = i

    c1 = 3*i + 1
    c2 = 3*i + 2
    c3 = 3*i + 3

    if c1 < size and A[c1] > A[largest]:
        largest = c1
    if c2 < size and A[c2] > A[largest]:
        largest = c2
    if c3 < size and A[c3] > A[largest]:
        largest = c3

    if largest != i:
        swap A[i] and A[largest]
        heapify(A, largest, size)
```

## Example

Let:

$$
A = [4, 9, 7, 1, 3, 6, 2]
$$

Construct a ternary heap:

$$
[9, 4, 7, 1, 3, 6, 2]
$$

Then repeatedly extract the maximum and restore the heap until sorted.

## Correctness

The heap property ensures that every parent node is greater than or equal to its children. The root is therefore the maximum element. Swapping it with the last element places it in its correct position. Repeating this process produces a sorted array.

## Complexity

| metric     | value         |
| ---------- | ------------- |
| build heap | $O(n)$        |
| extraction | $O(n \log n)$ |

Height:

$$
O(\log_3 n)
$$

Each heapify step examines up to three children, so comparisons per level increase slightly.

Total complexity remains:

$$
O(n \log n)
$$

## Properties

| property              | value                  |
| --------------------- | ---------------------- |
| stable                | no                     |
| in-place              | yes                    |
| branching factor      | 3                      |
| height                | lower than binary heap |
| comparisons per level | higher                 |

## Notes

Ternary heapsort trades fewer levels for more comparisons at each level. In practice, performance depends on hardware and data patterns. Binary heaps are more common, but higher arity heaps can perform better in some environments.

This idea generalizes to $d$-ary heaps, where each node has $d$ children.

## Implementation

```python id="k3v7px"
def ternary_heapsort(a):
    n = len(a)

    def heapify(i, size):
        largest = i
        c1 = 3 * i + 1
        c2 = 3 * i + 2
        c3 = 3 * i + 3

        if c1 < size and a[c1] > a[largest]:
            largest = c1
        if c2 < size and a[c2] > a[largest]:
            largest = c2
        if c3 < size and a[c3] > a[largest]:
            largest = c3

        if largest != i:
            a[i], a[largest] = a[largest], a[i]
            heapify(largest, size)

    for i in range((n - 2) // 3, -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="z8m4qt"
func TernaryHeapSort(a []int) {
	n := len(a)

	var heapify func(int, int)
	heapify = func(i, size int) {
		largest := i

		c1 := 3*i + 1
		c2 := 3*i + 2
		c3 := 3*i + 3

		if c1 < size && a[c1] > a[largest] {
			largest = c1
		}
		if c2 < size && a[c2] > a[largest] {
			largest = c2
		}
		if c3 < size && a[c3] > a[largest] {
			largest = c3
		}

		if largest != i {
			a[i], a[largest] = a[largest], a[i]
			heapify(largest, size)
		}
	}

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

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