完全二叉树

/*
 * Assume the size of an array is 9, e.g.
 *
 * Array: a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] // n = 9
 *
 * Heap :        a[0]               --- Level 0 ---
 *                / \
 *               /   \
 *              /     \
 *            a[1]    a[2]          --- Level 1 ---
 *            / \      / \
 *           /   \    /   \
 *         a[3] a[4] a[5] a[6]      --- Level 2 ---
 *         /  \
 *       a[7] a[8]                  --- Level 3 ---
 *
 * For node a[i],  i = 0, 1, 2, ..., N-1
 *
 *       Index of its Left  Child = (i + 1) * 2 - 1 = i * 2 + 1
 *       Index of its Right Child = (i + 1) * 2     = i * 2 + 2
 *       Index of its Parent      = (i + 1) / 2 - 1 = (i - 1) / 2

堆排序

什么是堆(Heap)？

堆本质上是一棵二叉树，而且是完全二叉树。 (注：从严格意义上讲，堆可以是N(>=2)叉树，为简单起见，这里只讨论堆为二叉树的情况。)
wiki_heap

堆的分类

堆分为大顶堆(Max Heap)和小顶堆(Min Heap)。
大顶堆： 大顶堆中的每个结点的关键值都不小于孩子结点(如果有的话)，根节点值最大
小顶堆：小顶堆中的每个结点的关键字都不大于孩子结点(如果有的话)，根节点值最小

堆到底有什么用？

堆(Heap)能很好地支持优先级队列(Priority Queue)的基本操作。 而优先级队列的应用是非常广泛的，例如：

*操作系统的调度器实现
*网络传输中的路由选择

什么是优先级队列(Priority Queue)？

优先级队列毫无疑问也是队列，表现形式为FIFO(Fisrt In, First Out)线性结构。但与普通队列不同的是，优先级队列的删除操作比较特殊，总是以队列元素的优先级高低为准，比如总是删除优先级最高的元素或者总是删除优先级最低的元素。而优先级队列的插入操作跟普通队列的插入操作一样，也就是不限制元素的优先级，任何时刻任何优先级的元素都可以入队。

堆排序(Heap Sort)的基本思想

堆排序(Heap Sort)是一种树形选择排序。

堆的构造：根据初始数组(a[0..n-1])构造一个完全二叉树，保证所有的父结点的关键字都>=它的孩子结点的关键字。
堆的析构：交换最后一个叶子结点(a[n-1])和树根结点(a[0])(关键字最大)，输出结点(a[n-1])，然后把余下的整棵树(a[0..n-2])重新调整为大顶堆。
将析构过程循环往复，当输出完最后一个结点后，这个数组(a[0..n-1])的关键字就满足从小到大的排列顺序了。

代码实现

extension Array where Element: Comparable {
    private mutating func exchange(_ i: Index, j: Index) {
        swapAt(i, j)
    }
    private func indexOfLeftChild(_ i: Index) -> Index {
        return 2 * i + 1
    }
    private func indexOfRightChild(_ i: Index) -> Index {
        return 2 * i + 2
    }
    private func indexOfParent(_ i: Index) -> Index {
        return (i - 1) / 2
    }
    /// 下游
    private mutating func sink(_ i: Index, _ n: Int) {
        var k = i
        while k < n / 2 {
            let left = indexOfLeftChild(k)
            let right = indexOfRightChild(k)
            var child = -1
            if left < n && right < n {
                child = (self[left] > self[right]) ? left : right
            } else if left < n && right >= n {
                child = left
            } else {
                child = k
            }
            if self[k] >= self[child] {
                break
            }
            exchange(k, j: child)
            k = child
        }
    }
    /// 上游
    private mutating func swim(_ i: Index) {
        var k = i
        while k != 0 {
            let parent = indexOfParent(k)
            if self[k] <= self[parent] {
                break
            }
            exchange(k, j: parent)
            k = parent
        }
    }
    private mutating func constructMaxHeap(_ n: Int) {
        for i in 0..<n {
            swim(i)
        }
    }
    mutating func heapSorts() {
        /// 构造maxHeap
        constructMaxHeap(count)
        var n = count
        while n > 0 {
            /// 交换maxValue与第n-1个
            exchange(0, j: n - 1)
            n -= 1
            /// 重新构造 构造后第0个为最大值
            sink(0, n)
        }
    }
    mutating func heapSort() {
        /// 构造maxHeap
        constructMaxHeap(count)
        var n = count
        while n > 0 {
            /// 交换maxValue与第n-1个
            exchange(0, j: n - 1)
            n -= 1
            /// 重新构造 构造后第0个为最大值
            constructMaxHeap(n)
        }
    }
}

引用

常见排序算法导读(8)[堆排序]