Heap sort

Problem¶

Implement in-place heap sort for a Python list.

Key trick¶

Build a max heap, repeatedly move its root to the end, and restore the heap.

Heap sort is inappropriate for linked lists because parent and child lookup requires efficient indexed access.

Trap¶

Heap construction is \(O(n)\), not \(O(n \log n)\), when performed bottom-up.

Why is it interesting?¶

It guarantees \(O(n \log n)\) time with \(O(1)\) auxiliary space, but it is unstable and generally slower than Python's built-in sort.

Python solution¶

class sorting_heap_sort:
    def sort(self, nums):
        n = len(nums)

        # Build a max heap bottom-up in O(n) time.
        # Nodes after `n // 2 - 1` are leaves and need no work.
        for i in range(n // 2 - 1, -1, -1):
            self._sift_down(nums, i, n)

        # Repeatedly move the heap maximum to the sorted suffix.
        for end in range(n - 1, 0, -1):
            nums[0], nums[end] = nums[end], nums[0]
            self._sift_down(nums, 0, end)

        return nums

    def _sift_down(self, nums, i, end):
        while 2 * i + 1 < end:
            j = 2 * i + 1
            if j + 1 < end and nums[j + 1] > nums[j]:
                j += 1
            if nums[i] >= nums[j]:
                break
            nums[i], nums[j] = nums[j], nums[i]
            i = j

Extra¶

Build a max heap bottom-up in O(n) time.¶

# Build a max heap bottom-up in O(n) time.
# Nodes after `n // 2 - 1` are leaves and need no work.
for root in range(n // 2 - 1, -1, -1):
    self._sift_down(nums, root, n)

I think the comment is wrong. It should be \(O(n \log n)\). Am I right?

No - the comment is correct. Bottom-up heap construction is \(O(n)\), not \(O(n \log n)\).

The subtlety is that although a single _sift_down operation can take \(O(\log n)\) time, most nodes are near the bottom of the tree and can only sift down a short distance.

For a heap of height \(h\):

Approximately \(\frac{n}{2}\) nodes are leaves, requiring no work.
Approximately \(\frac{n}{4}\) nodes are one level above the leaves, requiring at most \(1\) step.
Approximately \(\frac{n}{8}\) nodes are two levels above the leaves, requiring at most \(2\) steps.
This pattern continues up the tree.
One node is at the root, requiring at most \(\log n\) steps.

Therefore, the total work is approximately

\[ \frac{n}{4}(1) + \frac{n}{8}(2) + \frac{n}{16}(3) + \cdots \]

The key is that this sum is \(O(n)\):

\[ \sum_{h=1}^{\log n} \frac{n}{2^{h+1}}h = n \sum_{h=1}^{\log n} \frac{h}{2^{h+1}} = O(n). \]

This follows because the infinite series

\[ \sum_{h=1}^{\infty} \frac{h}{2^h} \]

converges to a constant.

Why the \(O(n \log n)\) intuition is tempting¶

If you built the heap by inserting elements one at a time:

for i in range(n):
    insert_into_heap(nums[i])

each insertion could cost \(O(\log n)\), resulting in a total time complexity of \(O(n \log n)\).

However, this code uses Floyd's bottom-up heap construction, which is specifically designed to build a heap in \(O(n)\) time.

Why `2*i` appears to compute children position in heap algorithm?¶

Because each previous parent (before i) occupies 2 child slots.

So starting from index 1 to index 2*i (including), there's 2*i children counting the parent from the tree root at index 0 up to the node i - 1.

The the slots 2*i + 1 and 2*i + 2 are for the children of the node i.