摘要：构建二叉树构建二叉树，就是把一个无序的完全二叉树调整为二叉堆，本质上就是让所有非叶子节点一次下沉上浮构建最大堆节点大的上浮，小的下沉构建最小堆节点小的上浮，大的下沉文章什么是二叉堆
什么是二叉堆
二叉堆的本质是一种完全二叉树，它分为两种类型：最大堆和最小堆
最大堆任何一个父节点的值，都大于等于它左右孩子的值，最小堆正好与之相反
二叉树的根节点叫做堆顶
最大堆和最小堆的特点是：最大堆的堆顶是整个堆中的最大元素，最小堆的堆顶是整个堆中的最小元素
堆的自我调整对于二叉堆有几种操作
插入节点
删除节点
构建二叉堆
这几种操作都是基于堆的自我调整
我们以最大堆为例，分析下堆的自我调整
插入节点二叉堆的节点插入位置是完全二叉树的最后一个位置，我们插入一个新节点，值为11。
这时候，我们让节点11和父节点5作比较，如果11大于5，则交换他俩交换位置，称为“上浮”
继续用节点11和父节点8进行比较，如果节点11大于节点8，则让节点11继续“上浮”
继续比较，最终让节点11上浮到堆顶位置
删除节点二叉树删除节点的过程和插入过程正好相反，它每次都是从堆顶删除，将堆顶的节点与与最后一个节点交换位置
然后将堆顶的节点5和它两个孩子进行比较，显然节点10比较打，让他俩交换位置，称为“下沉”
继续让节点5和它的孩子做比较，显然大的是节点8，让节点5继续下沉
此时就重新构建的二叉树。
构建二叉树构建二叉树，就是把一个无序的完全二叉树调整为二叉堆，本质上就是让所有非叶子节点一次下沉（上浮）
构建最大堆：节点大的上浮，小的下沉
构建最小堆：节点小的上浮，大的下沉
文章：什么是二叉堆？
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/97305.html
摘要：二叉堆的有趣之处在于，其逻辑结构上像二叉树，却是用非嵌套的列表来实现。二叉堆结构性质为了更好地实现堆，我们采用二叉树。图完全二叉树有意思的是我们用单个列表就能实现完全树。下列所示的代码是完全二叉堆的实现。 优先队列的二叉堆实现 在前面的章节里我们学习了先进先出（FIFO）的数据结构：队列（Queue）。队列有一种变体叫做优先队列（Priority Queue）。优先队列的出队（Dequ...
摘要：模型优先队列是允许至少下列两种操作的数据结构以及找出返回并删除优先队列中最小的元素。左式堆也是二叉树，左式堆和二叉堆的唯一区别是左式堆不是理想平衡，而实际上趋向于非常不平衡。事实上，沿左式堆的右路径是该堆中的最短路径。 6.1 模型 优先队列是允许至少下列两种操作的数据结构：insert 以及 deleteMin（找出、返回并删除优先队列中最小的元素）。 insert 操作等价于 en...
摘要：二叉树二叉树是一种树形结构，它的特点是每个节点最多只有两个分支节点，一棵二叉树通常由根节点，分支节点，叶子节点组成。 二叉树 二叉树(Binary Tree)是一种树形结构，它的特点是每个节点最多只有两个分支节点，一棵二叉树通常由根节点，分支节点，叶子节点组成。而每个分支节点也常常被称作为一棵子树。 showImg(https://segmentfault.com/img/bVbmEd...
摘要：二叉堆数据结构是一种特殊的二叉树，他能高效快速的找出最大值和最小值，常应用于优先队列和著名的堆排序算法中。 二叉堆数据结构是一种特殊的二叉树，他能高效、快速的找出最大值和最小值，常应用于优先队列和著名的堆排序算法中。 二叉堆 二叉堆有以下两个特性： 是一颗完全二叉树，表示数的每一层都有左侧和右侧子节点（除最后一层的叶节点），并且最后一层的叶节点尽可能是左侧子节点 二叉堆不是最小堆就是...
阅读 2625·2021-11-23 09:51
阅读 859·2021-09-24 10:37
阅读 3609·2021-09-02 15:15
阅读 1961·2019-08-30 13:03
阅读 1881·2019-08-29 15:41
阅读 2623·2019-08-29 14:12
阅读 1423·2019-08-29 11:19
阅读 3299·2019-08-26 13:39
