# Weak Heapsort

# Weak Heapsort

Weak heapsort is a heapsort variant that uses a weak heap instead of an ordinary binary heap. A weak heap stores elements in an implicit array and uses one extra reverse bit per node to define a modified tree structure.

The main advantage is comparison efficiency. Weak heapsort can use fewer comparisons than standard binary heapsort while still sorting in place.

## Problem

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

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

## Idea

A weak heap is a relaxed binary heap. It maintains enough order to make the root contain the maximum element, but it uses a different parent-child structure controlled by reverse bits.

For max weak heaps, the root remains the maximum element. Sorting proceeds like heapsort:

1. build a weak heap
2. repeatedly move the maximum to the end
3. restore the weak heap property

## Weak Heap Property

For every node except the root, the value at its distinguished ancestor is at least as large as the value at the node.

Informally, each node has a controlling ancestor that dominates it:

$$
A[parent^*(i)] \ge A[i]
$$

where $parent^*(i)$ is the node's weak heap parent.

## Algorithm

```text id="w5n2ks"
weak_heapsort(A):
    reverse = array of false bits

    build_weak_heap(A, reverse)

    for last from n - 1 down to 1:
        swap A[0] and A[last]
        restore_weak_heap(A, reverse, last)
```

A central operation is join.

```text id="x3p8qa"
join(A, reverse, i, j):
    if A[i] < A[j]:
        swap A[i] and A[j]
        reverse[j] = not reverse[j]
        return true

    return false
```

The join operation compares a parent-like node with a child-like node and restores the local weak heap relation.

## Example

Let:

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

After weak heap construction, the maximum is placed at the root:

$$
[10, \dots]
$$

Then weak heapsort repeatedly swaps the root with the last active element:

| step | action                                    |
| ---- | ----------------------------------------- |
| 1    | move maximum 10 to the final position     |
| 2    | restore weak heap on the remaining prefix |
| 3    | move next maximum to its final position   |
| 4    | continue until sorted                     |

Final result:

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

## Correctness

The weak heap invariant ensures that the root contains the maximum element of the active range. Each extraction swaps that maximum into its final sorted position. The restore operation rebuilds the weak heap property over the remaining active range. Repeating this process places elements from largest to smallest into their final positions, so the resulting array is sorted.

## Complexity

| metric           | value         |
| ---------------- | ------------- |
| build heap       | $O(n)$        |
| extraction phase | $O(n \log n)$ |
| total time       | $O(n \log n)$ |
| extra space      | $O(n)$ bits   |

The extra space is usually one bit per element for reverse bits. In some implementations, the bits can be packed.

## Properties

| property         | value                        |
| ---------------- | ---------------------------- |
| stable           | no                           |
| in-place         | almost                       |
| comparison based | yes                          |
| worst case time  | $O(n \log n)$                |
| comparisons      | fewer than standard heapsort |

## Notes

Weak heapsort is mainly interesting when comparison count matters. It has the same asymptotic complexity as heapsort but can have better comparison bounds.

The implementation is more subtle than ordinary heapsort, so ordinary binary heapsort is usually preferred for teaching and simple code.

## Implementation

This simplified implementation keeps the heap structure ordinary but separates the comparison-repair operation in a weak-heap style. A full weak heap implementation requires reverse bits and distinguished ancestors.

```python id="m7s2qd"
def weak_heapsort(a):
    n = len(a)
    reverse = [False] * n

    def join(i, j):
        if a[i] < a[j]:
            a[i], a[j] = a[j], a[i]
            reverse[j] = not reverse[j]
            return True
        return False

    def heapify(i, size):
        while True:
            largest = i
            left = 2 * i + 1
            right = 2 * i + 2

            if left < size and a[left] > a[largest]:
                largest = left
            if right < size and a[right] > a[largest]:
                largest = right

            if largest == i:
                break

            join(i, largest)
            i = largest

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

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

    return a
```

```go id="p9v4kx"
func WeakHeapSort(a []int) {
	n := len(a)
	reverse := make([]bool, n)

	join := func(i, j int) bool {
		if a[i] < a[j] {
			a[i], a[j] = a[j], a[i]
			reverse[j] = !reverse[j]
			return true
		}
		return false
	}

	heapify := func(i, size int) {
		for {
			largest := i
			left := 2*i + 1
			right := 2*i + 2

			if left < size && a[left] > a[largest] {
				largest = left
			}
			if right < size && a[right] > a[largest] {
				largest = right
			}

			if largest == i {
				break
			}

			join(i, largest)
			i = largest
		}
	}

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

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