美文网首页Aha! Algorithms
Aha! Algorithms - Heap

Aha! Algorithms - Heap

作者: su3 | 来源:发表于2017-03-21 22:17 被阅读0次

《啊哈!算法》第 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

相关文章

  • Aha! Algorithms - Heap

    《啊哈!算法》第 7 章第 3 节,创建最小堆的 Swift 实现。 问题 把一个数组转换为最小堆,并从小到大输出...

  • Aha! Algorithms

    1. 涉及的数据结构 栈、队列、链表、树、并查集、堆、图 2. 涉及的算法 排序、枚举、深度和广度优先搜索、图的遍...

  • Aha! Algorithms - Quicksort

    《啊哈!算法》第 1 章第 3 节,快速排序的 Swift 实现 问题 为给定数字序列排序 解决 以左侧第一个位置...

  • Aha! Algorithms - Queue

    《啊哈!算法》第 2 章第 1 节,队列的 Swift 实现 问题 给一个数字序列,解密方法是:删除第 1 个,将...

  • Aha! Algorithms - Dijkstra

    《啊哈!算法》第 6 章第 2 节,Dijkstra 算法求最短路径的 Swift 实现。 问题 已经若干顶点和路...

  • Aha! Algorithms - Floodfill

    《啊哈!算法》第 4 章第 5 节,漫水填充法的 Swift 实现。 问题 给一个群岛地图中不同的岛屿填充不同的颜...

  • Aha! Algorithms - Bomberman

    《啊哈!算法》第 3 章第 2 节,bomb 人的 Swift 实现。 问题 在哪里放置 bomb 才可以消灭最多...

  • Aha! Algorithms - Stack

    《啊哈!算法》第 2 章第 2 节,栈的 Swift 实现。 问题 判断字符串是否回文 解决 将字符串前半部分入栈...

  • Aha! Algorithms - Bucket Sort

    《啊哈!算法》第 1 章第 1 节,桶排序的 Swift 实现 问题 班上 5 个同学的考试成绩分别为:5 分,3...

  • Aha! Algorithms - Bubble Sort

    《啊哈!算法》第 1 章第 2 节,冒泡排序的 Swift 实现 问题 给学生成绩排序,打印排序后的名字(和成绩)...

网友评论

    本文标题:Aha! Algorithms - Heap

    本文链接:https://www.haomeiwen.com/subject/ezhnnttx.html