认识二叉堆

作者: Uzero | 来源:发表于2018-10-06 14:02 被阅读0次

什么是二叉堆？

二叉堆本质上是一种完全二叉树( 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树)，它分为两个类型：

二叉堆的根节点叫做堆顶

最大堆：最大堆当中任何一个父节点的值，都大于等于它左右孩子节点的值。最大堆的堆顶是整个堆中的最大元素

最大堆

最小堆：最小堆当中任何一个父节点的值，都小于等于它左右孩子节点的值。最小堆的堆顶是整个堆中的最小元素

最小堆

堆的自我调整：

一、插入节点

二叉堆节点的插入，插入位置是完全二叉树的最后一个位置。

二、删除节点

二叉堆节点的删除过程和插入过程正好相反，所删除的是处于堆顶的节点。

三、构建二叉堆

构建二叉堆，也就是把一个无序的完全二叉树调整为二叉堆，本质上就是让所有非叶子节点依次下沉。

二叉堆虽然是一颗完全二叉树，但它的存储方式并不是链式存储，而是顺序存储。换句话说，二叉堆的所有节点都存储在数组当中。

数组中，在没有左右指针的情况下，如何定位到一个父节点的左孩子和右孩子呢？

假设父节点的下标是index，那么它的左孩子下标就是 2*index+1；它的右孩子下标就是 2*index+2 。

如下图节点6包含9和10两个孩子，节点6在数组中的下标是3，节点9在数组中的下标是7，节点10在数组中的下标是8。7 = 3*2+1 8 = 3*2+2