数据结构之——堆
数据结构堆:
堆的定义:
堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:
Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]
即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。堆分为大顶堆和小顶堆,满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆,满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的,小顶堆的堆顶的关键字是所有关键字中最小的。
用数组表示堆:
(引自http://sauron.blog.51cto.com/5231038/1227373)
用数组表示完全二叉树:一个完全二叉树在其倒数第二层以上是满的,并且其最后一层上的叶子结点是从左到右填满的。因此,指导最后一片叶子,完全二叉树中没有空洞。
如果一颗二叉树是完全的,使用数组而不是链表会更好。可以使用层序遍历将这棵二叉树的数据存放到一个数组中的连续位置。这种表示可以容易地找到一个结点的双亲或孩子中的数据。如果从数组的索引1开始存放二叉树,即跳过数组的第一个位置,则数组索引i处结点的:双亲在索引i/2处,除非该结点是根节点(i为1);子结点在索引2i与2i+1处。
堆的相关操作:
向堆中插入元素:
避免交换
为了将新元素插入堆,要从下一个可用于叶子的空闲位置开始。跟踪从该叶子到根的路径,直到找到新元素的正确位置。在这样做的同时,将元素从双亲向子结点移动以便最终为新元素腾出空间。
删除堆的根:
删除根算法
创建堆:
方法1:插入法:
从空堆开始,依次插入每一个结点,直到所有的结点全部插入到堆为止。
时间:O(n*log(n))
从空堆开始,依次插入每一个结点,直到所有的结点全部插入到堆为止。
时间:O(n*log(n))
方法2:调整法:
序列对应一个完全二叉树;从最后一个分支结点(n div 2)开始,到根(1)为止,依次对每个分支结点进行调整(下沉),以便形成以每个分支结点为根的堆,当最后对树根结点进行调整后,整个树就变成了一个堆。
时间:O(n)
对如图的序列,要使其成为堆,我们从最后一个分支结点(10/2),其值为72开始,依次对每个分支节点53,18,36 45进行调整(下沉).
序列对应一个完全二叉树;从最后一个分支结点(n div 2)开始,到根(1)为止,依次对每个分支结点进行调整(下沉),以便形成以每个分支结点为根的堆,当最后对树根结点进行调整后,整个树就变成了一个堆。
时间:O(n)
对如图的序列,要使其成为堆,我们从最后一个分支结点(10/2),其值为72开始,依次对每个分支节点53,18,36 45进行调整(下沉).
两种方法详细对比参考:
http://shmilyaw-hotmail-com.iteye.com/blog/1776612