Heap Sort 堆排序

1. 堆的定义

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: In a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C.

1.1 数据结构

堆通常使用完全二叉树来实现并且完全二叉树可以使用数组来表示，故堆可以使用数组来实现。

堆的类型通常有两种：

1. 最大堆：父节点的元素一定大于等于子节点
2. 最小堆：父节点的元素一定小于等于子节点

数组中节点的关系

在用数组表示的堆中，假设当前节点为$N_i$，i为数组索引，则有：

1. 父节点索引为：$\frac{i-1}{2}$
2. 左子节点索引为：$2i+1$
3. 右子节点索引为：$2i+2$

2. 堆排序

In computer science, heapsort is a comparison-based sorting algorithm.

Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region.

排序流程：

1. Call the buildMaxHeap() function on the list. Also referred to as heapify(), this builds a heap from a list in $O(n)$ operations.
2. Swap the first element of the list with the final element. Decrease the considered range of the list by one.
3. Call the siftDown() function on the list to sift the new first element to its appropriate index in the heap.
4. Go to step (2) unless the considered range of the list is one element.

伪代码：

(Put elements of 'a' in heap order, in-place)
procedure heapify(a, count) is
    (start is assigned the index in 'a' of the last parent node)
    (the last element in a 0-based array is at index count-1; find the parent of that element)
    start ← iParent(count-1)
    
    while start ≥ 0 do
        (sift down the node at index 'start' to the proper place such that all nodes below
         the start index are in heap order)
        siftDown(a, start, count - 1)
        (go to the next parent node)
        start ← start - 1
    (after sifting down the root all nodes/elements are in heap order)

(Repair the heap whose root element is at index 'start', assuming the heaps rooted at its children are valid)
procedure siftDown(a, start, end) is
    root ← start

    while iLeftChild(root) ≤ end do    (While the root has at least one child)
        child ← iLeftChild(root)   (Left child of root)
        swap ← root                (Keeps track of child to swap with)

        if a[swap] < a[child] then
            swap ← child
        (If there is a right child and that child is greater)
        if child+1 ≤ end and a[swap] < a[child+1] then
            swap ← child + 1
        if swap = root then
            (The root holds the largest element. Since we assume the heaps rooted at the
             children are valid, this means that we are done.)
            return
        else
            Swap(a[root], a[swap])
            root ← swap          (repeat to continue sifting down the child now)

3. 算法复杂度

时间复杂度(Time Complexity):

• 最坏(Worst-case): $O(nlogn)$
• 最好(Best-case): $O(n)$ or $O(nlogn)$ ；数组元素全部相同，$O(n)$，数组元素全不同，$O(nlogn)$
• 平均(Average): $O(nlogn)$；构建堆$O(n)$，每次节点下沉$O(nlogn)$，总体：$O(nlogn)=O(n)+O(nlogn)$

空间复杂度(Space Complexity): $O(1)$

4. 实现

func heapSort(nums []int) {
    initHeap(nums) // heapify
    for i := len(nums)-1; i >= 0; i-- {
        swap(0, i, nums)
        down(0, i, nums)
    }
}

func initHeap(nums []int) { // O(n)
    n := len(nums)
    for i := n/2 - 1; i >= 0; i-- {
        down(i, n, nums)
    }
}

func down(i, n int, nums []int) {
    for {
        j := i*2 + 1
        if j >= n || j < 0 { // j < 0, overflow
            break
        }
        if j2 := j+1; j2 < n && nums[j] < nums[j2] {
            j = j2
        }
        
        if nums[i] >= nums[j] {
            break
        }
        swap(i, j, nums)
        i = j
    }
}

func swap(i, j int, a []int) {
    a[i], a[j] = a[j], a[i]
}

5. Leetcode

912. 排序数组

Reference

1. https://en.wikipedia.org/wiki/Heapsort
2. https://en.wikipedia.org/wiki/Heap_(data_structure)
3. https://github.com/golang/go/blob/release-branch.go1.20/src/container/heap/heap.go