数据结构之「堆」

作者: 清尘闲聊 | 来源:发表于2019-04-18 11:54 被阅读1次

    堆 是一种特殊的完全二叉树结构,通常,它有两种类型:最小堆 和 最大堆。

    最小堆(min heap)是父节点的值恒小于等于子节点的值。

    image

    最大堆(max heap)是父节点的值恒大于等于子节点的值。

    image

    二叉堆的性质

    任意节点小于(或大于)它的所有子节点,最小值(或最大值)在堆的根上。
    堆总是一棵完全树。即除了最底层,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。

    二叉堆的实现

    堆的存储结构

    堆一般可以用数组的方式来存储,数组的顺序其实就是堆层级遍历的结果。

    堆的插入

    由于堆是一个完全二叉树,每次总是先填满上一层,再在下一层从左往右依次插入。

    插入步骤:
    1.首先将新元素增加到堆的末尾。
    2.然后在新元素与其父节点的值比较,如果新元素小于父节点的值则将两者交换位置。
    3.不断进行第2步操作,直到不需要交换元素,或者达到堆顶。

    最后就会得到一个最小堆,上面交换元素的过程叫做上滤。

    堆的删除

    堆的删除和插入操作是刚刚相反的,插入是从下往上调整堆,删除是从上往下调整堆。

    删除步骤:
    1.首先删除堆顶元素。
    2.然后在比较左右子节点,将小的元素上调。
    3.不断进行步骤2,直到不需要调整或者调整到堆底了。

    上面交换元素的过程叫做下滤。

    总结

    堆有两种类型,最大堆和最小堆,并且堆总是一颗完全树。

    由于堆的 父节点的值恒小于等于子节点的值 或者 父节点的值恒大于等于子节点的值,可以作为 Top n 使用。

    堆(通常是二叉堆)常用于排序。这种算法称作堆排序。

    PS:
    清山绿水始于尘,博学多识贵于勤。
    我有酒,你有故事吗?
    微信公众号:「清尘闲聊」。
    欢迎一起谈天说地,聊代码。

    相关文章

      网友评论

        本文标题:数据结构之「堆」

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