算法笔记-二叉堆

MrZONT 发布于2019-08-15 18:09 / 1179人阅读

摘要：二叉堆的概念二叉堆是一种特殊的二叉树。二叉堆分为两种最大堆和最小堆，最大堆的父节点一定大于其子节点根节点最大，最小堆的父节点小于其子节点根节点最小。这是我对二叉堆的理解，如有不对，欢迎指正，我会立即修改，谢谢。

二叉堆的概念

二叉堆是一种特殊的二叉树。二叉树是每个节点只有两个子节点的树（应该都懂吧）。二叉堆分为两种：最大堆和最小堆，最大堆的父节点一定大于其子节点（根节点最大），最小堆的父节点小于其子节点（根节点最小）。

下面是一个二叉树：

我们用一维数组将二叉树初始化，例如：我们有{1，2，3，4，5，6，7}七个数要放入堆中，第一步初始化数组的长度大于8，array[0]为null，array[1]~array[7]放入数字。

为什么array[0]为null呢？因为要用下标值找到它的子节点和父节点，比如a[1]=1,a[2]=2,a[3]。我们知道a[1]的子节点是a[2],a[3],由于是二叉树，a[k]的子节点一定是a[2k]和a[2k+1],a[k]的父节点一定是a[k/2]。花个20秒思考一下吧。

图示：

将一个二叉树变成二叉堆

我以最大堆为例，最大堆的定义是：父节点的value一定要大于子节点的value。

1.子节点的value大于父节点的value的情况

此时T大于P，违反了最大堆的平衡性，所以要将T和其父节点对调

但是T移动到了P的位置后，它的值依然比其父节点要大，还要上浮

最终T移动到了根节点，最大堆平衡了

代码如下：


public void swim(int k) {
        while (k > 1 && less(k / 2, k)) {
            exch(k / 2, k);
            k = k / 2;
        }
    }

2. 父节点的value小于子节点的value的情况

此时，H比子节点要小，H要下沉，先比较P和S谁比较大，跟大的换位置

跟S换之后，发现依然比子节点要小，还是要下浮，最后

下沉的代码如下：

public void sink(int k) {
//判断是否超过数组最大长度
    while (2 * k < N) {
    //找到子节点
        int j = 2 * k;
        //两个子节点进行比较，选大的
        if (j < N && less(j, j + 1)) j++;
        //没有比子节点小，就跳出循环
        if (!less(k, j)) break;
        exch(k, j);
        k = j;
    }
}

上浮和下沉的应用（敲黑板，重点）

向数组插入value会用到上浮

每次向队尾插入一个value时，都要检查是否违反最大堆的平衡性。

删除根节点时，会用到下沉

每次想删除根节点，第一步是要将跟节点与最后一个节点互换位置后，将其删除，此时最后一个节点作为根节点，一定会比子节点要小，违反平衡性，那就下浮

堆排序

很简单，最大堆为例，根节点是最大的节点，每次将根节点和最后一个子节点对调位置，此时数组的最后一位即为最大，待其最大堆再次平衡时，再将根节点和最后一个子节点对调，即为排序。例如：

    数组元素为{a,b,c,d,e},假设二叉堆已经平衡，a为根节点，也就是最大的节点,将a和e对调，
    {e,b,c,d,a},数组的长度此时应该减一，将数组的前四位进行二叉堆的平衡，e肯定要下沉到相应位置，然后再将根节点和长度减一后的最后一个节点对调位置。

这是我对二叉堆的理解，如有不对，欢迎指正，我会立即修改，谢谢。

专线服务混合云二叉堆二叉树算法最优二叉树算法图求二叉

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69648.html

数据结构与算法学习笔记 - 优先队列、二叉堆、左式堆

摘要：模型优先队列是允许至少下列两种操作的数据结构以及找出返回并删除优先队列中最小的元素。左式堆也是二叉树，左式堆和二叉堆的唯一区别是左式堆不是理想平衡，而实际上趋向于非常不平衡。事实上，沿左式堆的右路径是该堆中的最短路径。 6.1 模型优先队列是允许至少下列两种操作的数据结构：insert 以及 deleteMin（找出、返回并删除优先队列中最小的元素）。 insert 操作等价于 en...

SunZhaopeng 2019-08-14 14:05 评论0 收藏0
【阅读笔记】——什么是二叉堆

摘要：构建二叉树构建二叉树，就是把一个无序的完全二叉树调整为二叉堆，本质上就是让所有非叶子节点一次下沉上浮构建最大堆节点大的上浮，小的下沉构建最小堆节点小的上浮，大的下沉文章什么是二叉堆什么是二叉堆二叉堆的本质是一种完全二叉树，它分为两种类型：最大堆和最小堆最大堆任何一个父节点的值，都大于等于它左右孩子的值，最小堆正好与之相反 showImg(https://segmentfault....

big_cat 2019-08-23 11:41 评论0 收藏0
JavaScript数据结构与算法（十一）二叉堆

摘要：二叉堆数据结构是一种特殊的二叉树，他能高效快速的找出最大值和最小值，常应用于优先队列和著名的堆排序算法中。二叉堆数据结构是一种特殊的二叉树，他能高效、快速的找出最大值和最小值，常应用于优先队列和著名的堆排序算法中。二叉堆二叉堆有以下两个特性：是一颗完全二叉树，表示数的每一层都有左侧和右侧子节点（除最后一层的叶节点），并且最后一层的叶节点尽可能是左侧子节点二叉堆不是最小堆就是...

MartinHan 2019-08-26 10:58 评论0 收藏0
《画解数据结构》九张图画解二叉堆

摘要：本文已收录于专栏画解数据结构前言在之前的文章二叉搜索树中，对于增删改查的时间复杂度为。从子结点个数上可以分为二叉堆，叉堆等等。本文将介绍的是二叉堆。有关完全二叉树的内容，可以参考画解完全二叉树。就是利用数组来表示链式结构。 ...

peixn 2021-11-18 10:02 评论0 收藏0
Python数据结构——二叉堆的实现

摘要：二叉堆的有趣之处在于，其逻辑结构上像二叉树，却是用非嵌套的列表来实现。二叉堆结构性质为了更好地实现堆，我们采用二叉树。图完全二叉树有意思的是我们用单个列表就能实现完全树。下列所示的代码是完全二叉堆的实现。优先队列的二叉堆实现在前面的章节里我们学习了先进先出（FIFO）的数据结构：队列（Queue）。队列有一种变体叫做优先队列（Priority Queue）。优先队列的出队（Dequ...

stackfing 2019-07-24 18:19 评论0 收藏0