堆_pas.pptVIP

堆——优先队列 堆的描述 堆的描述 ?习惯上，我们将二叉堆简称为“堆”，二叉堆是以数组存储的完全二叉树，是一种实现优先队列（priority queue）的数据结构。优先队列是至少允许插入(insert)和删除最小项（或最大项）（deleteMin or deleteMax）两种操作，有时我们可以添加一些其他的操作，但不属于优先队列基本模型的一部分。 堆的定义 n个元素称为堆，当且仅当它的关键字序列满足： 或满足： 满足式（1）的称为最小堆（也称小根堆），满足式（2）的称为最大堆（也称大根堆）。形象地说，父节点值大于或等于其孩子节点值的，叫最大堆；父节点值小于或等于孩子节点值的，叫最小堆。 堆是一颗完全二叉树。 堆的性质 设树的高度为d，则堆具有如下的几个性质： 所有的叶结点不是处在第d层，就是处于第d-1层（完全二叉树性质）； 当d≥1时，第d-1层上有 个结点（完全二叉树性质）； 第d-1层上如果有分支结点，则这些分支结点都集中在树的最左边（完全二叉树性质）； 每个结点所存放元素的关键字，都大于（最大堆）或小于（最小堆）它的子孙结点所存放元素的关键字（堆性质）。 堆得深度为 log2(n) 堆的存储特点 由于堆是一颗完全二叉树，根据完全二叉树的性质，可以用数组来存储堆。对于图1，将这两个堆保存在以1开始的数组中： 按照这种存储方式，可知第i个元素的左右儿子分别是第2i和第2i+1个元素，而它的父亲节点是第i/2个元素。由于父亲节点和儿子节点具有这样的顺序关系，所以可以方便地由父亲节点找到儿子节点，反之亦然。可见，相对于链表存储方式，这种存储方式大大节省了存储空间，高效快速。 在数组的存储方式下，堆有如下性质： 当用数组表示存储了n个元素的堆时，叶子结点的下标是： ； 一个从小到大已排好序的数组是最小堆，反之则不然，因为堆的结构不唯一； 一个最大堆（最小堆）中最小（最大）元素在堆的叶子结点上。 二、堆的相关操作 基本操作 堆作为一种优先队列的数据结构，其基本操作是：插入（入队）和删除最大项或最小项（优先级最低或最高的项出队）；下面是堆的一些常用操作 (n为堆元素个数)。为了便于描述，假定这里的堆都是最大堆（最小堆的操作与最大堆类似）。 在实际实现中，我习惯把堆定义成全局变量 基本操作 上移：procedure sift_up(i:longint)；提升堆中第i个元素优先级； 下移：procedure sift_down(i:longint)；降低堆中第i个元素的优先级； 插入：procedure insert(x:ElementType)；把元素x插入堆中，即入队列； 删除第i项：procedure delete(i:longint)；删除堆中第i个元素； 删除堆顶：function delete_max:ElemntType；从非空的最大堆中删除并回送关键字最大的元素，即出队列； 建堆：procedure make_heap；使数组H中的元素按堆的结构重新组织。 N是堆的 大小。作为全局变量更容易控制。 上移 当修改堆中某个元素的关键字，使其大于它父亲的关键字时，就违反了最大堆的性质。为了重新恢复最大堆的性质，需要把这个元素上移到它的合适位置，这时，使用sift_up操作。操作描述如下（swap（a，b）为交换两个元素a，b值的过程）： 输入：数组H[]及被上移的元素下标i； 输出：维持堆的性质的数组H[]。 举例 例如，图1.1中，把结点9的内容改为28，这样就破坏了最大堆的性质。为了恢复最大堆的性质，需要对结点9进行sift_up操作，图1.2表明了这种sift_up操作的工作过程。 代码 procedure sift_up(i:longint)； begin while (i0) do begin if H[i]H[i div 2] then swap(H[i],H[i div 2]) else break; i:=i div 2; end; end; 分析： 元素每进行一次移动，就执行一次比较操作，如果移动成功，它所在结点的层数就减1。n个元素共有 层结点，所以sift_up操作最多执行 次比较操作，由此，sift_up操作的执行时间是 。所需要的工作单元个数为 。 下移 同理，当修改堆中某