《啊哈！算法》第 7 章第 3 节，创建最小堆的 Swift 实现。
问题
把一个数组转换为最小堆，并从小到大输出。
解决
从最后一个非子节点开始，与它的左右子儿子比较，将最小值放到上面，循环遍历所有非子节点。
//用一个一维数组存储完全二叉树
var heap = [99, 5, 36, 7, 22, 17, 92, 12, 2, 19, 25, 28, 1, 46]
var count = heap.count
//向上（更小编号）调整，把小的值放到父节点，目标是建立最小堆
func siftup(i: Int){
var idx = i
var tmp = 0
var flag = 0 //是否要继续调整
//当节点至少有左儿子的时候执行循环
while idx * 2 + 1 < count && flag == 0{
//判断当前节点与左儿子的大小，tmp 记录较小结点的编号
if heap[idx] > heap[idx * 2 + 1] {
tmp = 2 * idx + 1
}else{
tmp = idx
}
//如果有右儿子，那么较小值与右儿子比较
if idx * 2 + 2 < count {
if heap[tmp] > heap[idx * 2 + 2] {
tmp = idx * 2 + 2
}
}
//如果当前节点不是最小，那么交换位置
if tmp != idx {
swap(&heap[tmp], &heap[idx])
idx = tmp //idx 与 tmp 交换了，更新 idx 为交换的儿子的编号，以便继续向上调整
}else{
//如果父节点比其他两个节点都小，就不需要再调整了
flag = 1
}
}
}
func delete() -> Int{
let tmp = heap[0] //记录最小值
heap[0] = heap[count-1] //把最大值放到编号0位置
count -= 1 //删除了原先 0 位置的值，数量减少了
siftup(i: 0) //从 0 开始调整
return tmp //输出最小值
}
//创建堆
func creat(){
//从最后一个非叶节点开始依次向上（更小编号）调整
for i in (0..<count/2).reversed() {
siftup(i: i)
}
}
creat()
print(heap)
for _ in 0..<count {
print("\(delete())", separator: "", terminator: " ")
}
堆排序算法由 J. W.J. Williams 于 1964 年发明。同年 Robert W. Floyd 提出了建立堆的线性时间算法。
代码在 GitHub
