HeapSort学习笔记
2018-11-30 本文已影响2人
zh_19
完全二叉树
/*
* 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)
}
}
}
