数据结构【五-2】:堆

堆的定义和插入删除


引用文章:

详解数据结构——堆

数据结构之堆(Heap)

数据结构浅析(10)-树性结构:堆

定义:堆是一种完全二叉树,对于任意一个结点来说,其值都大(小)于其任意一个子节点的值,称为最大(小)堆

因为完全二叉树有其非常卓越的性质:对于任意一个父节点的序号n来说(这里n从0算),它的子节点的序号一定是2n+1,2n+2,因此我们可以直接用数组来表示一个堆

插入:在堆中插入一个结点就是将该元素插入到堆的尾部,然后不断上浮调整位置,直至满足堆的条件。

POP根结点:删除堆顶元素后,用末尾元素补上,个数减1(这样才能用数组表示删除了一个节点),然后不断下沉,直至满足堆的条件。

初始化: 首先:数据输入,构建完全二叉树

一个单独的节点就可以看成是一个最大堆了,如果我们用数组存放,那么由完全二叉树特点,后n/2个数为叶子。

所以我们从第n/2个数据开始向上到根结点,我们可以将其最为一个子树的根,将这个子树视为刚刚删除一个根节点的堆,用POP根节点后的操作进行该子堆重构,这样操作保证了每一个子树都是堆,然后由小到大,保证了最终构成了堆,这样就不用再次检验是否是堆了,若对从2/n到1的节点只判断节点和左右子节点是否要交换,最后还需要再次判断是否是堆,并继续调整

堆排序


将数据改造为最大堆或者最小堆,不断重复输出根节点(但是操作换为最后一个元素和根元素互换),重新构建堆(也就是POP根节点操作)这样下去,最终就能在原有数组得到一个有序序列

根据特性我们能推出:升序使用大顶堆,降序使用小顶堆

详解:[图解排序算法(三)之堆排序]

-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享,您的支持将鼓励我继续创作!恰饭^.^~