--------------------siwuxie095

堆的基本存储

在堆中实现的插入操作和删除操作，都是 logN 级别的，

显然，堆一定相应的是一个树形结构，最为经典的一种

堆的实现叫做 二叉堆（Binary Heap）

二叉堆对应的是二叉树，所谓二叉树，就是每一个节点，

最多有两个子节点

那么这个二叉树有什么特点呢？ 分为两种情况：

（一）最大堆

1）它的任何一个节点都不大于它的父节点

2）它必须是一棵完全二叉树

满足上面两个性质的二叉树，称为 最大堆

也即

1）堆中某个节点的值总是不大于其父节点的值

2）堆总是一棵完全二叉树

（二）最小堆

1）它的任何一个节点都不小于它的父节点

2）它必须是一棵完全二叉树

满足上面两个性质的二叉树，称为 最小堆

也即

1）堆中某个节点的值总是不小于其父节点的值

2）堆总是一棵完全二叉树

『所谓完全二叉树，即 除了最底层，其它层的节点

都被元素填满，且最底层尽可能地从左到右填入』

下面以最大堆为例进行介绍：

最大堆在计算机上的一种实现：用数组存储二叉堆

可能很多人都曾经实现过一棵树，觉得既然堆是一个树形结构，就应该

采用链表的形式，设立一个节点，这个节点有左右两个指针分别指向它

的左右孩子，这样可以实现一个堆

不过，对于堆而言，有一个非常经典的实现，这种实现方式是使用数组

来存储一个二叉堆

之所以可以使用数组来存储一个二叉堆，正是因为堆是一棵完全二叉树

对这颗完全二叉树，自上到下、自左到右的给每一个节点标上一个序列

号，即 依照层序自上到下、之后在每一层自左到右的标上序列号

「序列号 即 索引」

如果第一个节点（根节点）的索引为 1，则：

对于每一个节点来说，相应的左孩子的索引就是自身索引的二倍，

而相应的右孩子的索引就是自身索引的二倍加一

注意：索引 0 是不使用的

通过如下公式，即可找到每个元素的双亲和左右孩子：

（1）parent ( i ) = i / 2

（2）left child ( i ) = 2 * i

（3）right child ( i ) = 2 * i + 1

如果第一个节点（根节点）的索引为 0，则：

对于每一个节点来说，相应的左孩子的索引就是自身索引的二倍加一，

而相应的右孩子的索引就是自身索引的二倍加二

通过如下公式，即可找到每个元素的双亲和左右孩子：

（1）parent ( i ) = ( i - 1 ) / 2

（2）left child ( i ) = 2 * i + 1

（3）right child ( i ) = 2 * i + 2

如何向最大堆中添加元素（即 插入）？

这里用到了一个核心操作，通常叫做 Shift Up

这个堆使用了数组进行表示，所以相应的，在最大堆中添加元素

就相当于在数组的末尾添加元素，但此时的堆可能不满足最大堆

的定义

所以要进行一系列的操作来维护堆的定义，具体应该怎么做呢？

其实这个过程非常简单，只需要把新加入的元素调整到一个合适

的位置，使得整个二叉树依然保持最大堆的性质

具体来说：将新加入的元素和父节点的元素进行比较，如果父节

点的元素比新加入的元素还要小，就交换位置

新加入的元素逐渐上移的过程，就是 Shift Up 的过程

如何从最大堆中取出元素（即 删除）？

这里用到了一个核心操作，通常叫做 Shift Down

如果要想从堆中取出元素，只能取出根节点的那个元素，对于最

大堆来说，就相当于取出了优先级最大的那个元素

此时，整个堆中相当于少了一个元素，怎么填补这个元素呢？

只需要把整个堆的最后一个元素放到整个堆的第一个元素（根节

点）的位置即可，但此时的堆可能不满足最大堆的定义

实际上是互换了位置，之后计数器 count--，无法访问原根节点

现在所在的位置，相当于少了一个元素，即被取出了

所以要进行一系列的操作来维护堆的定义，具体应该怎么做呢？

其实这个过程非常简单，只需要把此时根节点的元素调整到一个

合适的位置，使得整个二叉树依然保持最大堆的性质

具体来说：比较左右孩子的元素，谁大就和谁交换位置

根节点的元素逐渐下移的过程，就是 Shift Down 的过程

最小堆的情况类似 …

【made by siwuxie095】

堆 续1