[理学]堆与互不相交集课件.pptVIP

（1）堆的定义 个元素称为堆，当且仅当它的关键字序列满足： 或者满足： 把式 的堆称为最小堆；把式 的堆称为最大堆。 由堆定义知：它是一棵完全二叉树。若树的高度为，则堆具有如下性质： 所有的叶子结点不是处在第 层，就是处在第 层。 当 时，第 层上的 个结点。 第 层上如果有分支结点，则这些分支结点都集中在树的最左边。 每个结点所存放元素的关键字，都大于(最大者)或小于(最小者)它子孙结点所存放元素的关键字。 对于一个具有 个元素的堆，可以很方便地用如下方法，由数组 来存放它： 根结点存放在 。 假定结点 存放在 ，如果它有左孩子结点，则其左孩子结点存放 ；如果它有右孩子结点，则其右孩子结点存放 。 非根结点 的父结点存放在 （2）举例:输入数据20，17，9，10，11，4，5，3，7，5 （3）堆的运算 sift_up[H,i]:将H[i]向上调整到合适的位置，使H成 为堆。 sift_down[H,i]:向下调整H[i]到合适的位置，使H成 为堆。 delete_max[H,i]:从堆H中删除第i项。 insert[H,x]:插入x到堆H中。 makeheap[A]:将数组A转换成堆。 过程 SIFT_UP 输入：数组H[1…n]及i，1?i?n 输出：上移H[i]，以使它不大于父结点 1 done=false 2 if i=1 then exit 3 repeat 4 if key(H[i])key(H[i/2]) then key(H[i])与key(H[i/2])交换 5 else done=true 6 i=?i/2? 7 until i=1 or done 过程 SIFT_DOWN 输入：数组H[1…n]及i，1?i?n 输出：下移H[i]，以使它不小于父结点 1 done=false 2 if 2in then exit 3 repeat 4 i=2i 5 if i+1?n and key(H[i+1])key(H[i]) then i=i+1 6 if key(H[i/2])key(H[i]) then key(H[i])与key(H[i/2])交换 7 else done=true 8 end if 9 until i=1 or done 算法4.1 INSERT 输入：堆H[1…n]和元素x 输出：新的堆H[1…n+1]，x为其元素之一 1 n=n+1 2 H[n]=x 3 SIFT_UP(H,n) 算法4.2 DELETE 输入：非空堆H[1…n]及i，1?i?n 输出：删除H[i]之后的新的堆H[1…n-1] 1 x=H[i];y=H[n] 2 n=n-1 3 if i=n+1 then exit 4 H[i]=y 5 if key(y)?key(x) then SIFT_UP(H,i) 6 else SIFT_DOWN(H,i) 7 end if 算法4.3 DELETE_MAX 输入：堆H[1…n] 输出：返回最大键值x并将其从堆删除H[1] 1 x=H[1] 2 DELETE(H,1) 3 return x 堆创建举例：输入序列4，38，10，1