堆及其应用江苏省华罗庚中学杨志军第一页,共三十九页。堆的定义01堆的性质02堆的基本操作03堆的应用04TableofContents内容大纲第二页,共三十九页。预备知识•完全二叉树:如果一棵深度为K的二叉树,1至K-1层的结点都是满的,即满足2i-1(1<=i<=k-1),只有最下面的一层的结点数小于等于2k-1,并且最下面一层的结点都集中在该层最左边的若干位置,则此二叉树称为完全二叉树。第三页,共三十九页。预备知识1234567满二叉树12345完全二叉树第四页,共三十九页。堆的定义•堆也称二叉堆,结构上是一种数组,本质上是一棵完全二叉树。树中每个结点与数组中存放该结点中值的那个元素相对应。第五页,共三十九页。堆的性质•树根为A[1],利用完全二叉树的性质,可以求出第i个结点的父结点、左孩子结点、右孩子结点的下标分别为:trunc(i/2)、2i、2i+1。第六页,共三十九页。堆的性质•二叉堆还具有这样一个重要的性质:对除根以外的每个结点i,A[parent(i)]≥A[i],即所有结点的值都不得超过其父结点的值,称为大根堆。小根堆就是要求:A[parent(i)]≤A[i]。第七页,共三十九页。堆的基本操作•使用堆的关键部分是两个基本操作:Put操作:即往堆中加入一个结点。方法是往堆尾加入一个结点,并通过从下往上的调整法,使其继续保持堆的性质;Get操作:即从堆中取出根结点。方法是从堆中取出堆头结点,并删除该结点(堆尾覆盖),再通过从上往下的调整法,使其继续保持堆的性质;第八页,共三十九页。Put操作575644321142564375heap第九页,共三十九页。Put操作14256437557561443211425643751heap第十页,共三十九页。Put操作14256437515756144321heap1425143756son第十一页,共三十九页。Put操作14251437565751644321heap1125443756son第十二页,共三十九页。Put操作11254437565754614321heapson第十三页,共三十九页。Put操作procedureput(x:longint);varfa,son,tmp:longint;beginlen:=len+1;heap[len]:=x;son:=len;while(son<>1)and(heap[sondiv2]>heap[son])dobegintemp:=heap[sondiv2];heap[sondiv2]:=heap[son];heap[son]:=temp;son:=sondiv2;end;end;第十四页,共三十九页。Put操作voidput(intx){intfa,son,tmp;len++;heap[len]=x;son=len;while(son!=1&&heap[son/2]>heap[son]){tmp=heap[son/2];heap[son/2]=heap[son];heap[son]=tmp;son=son/2;}}第十五页,共三十九页。Get操作11254437565754614321heap第十六页,共三十九页。Get操作11254437565754614321heap612544375第十七页,共三十九页。Get操作612544375575414326heap162544375pa第十八页,共三十九页。Get操作162544375575464321heap142564375pa第十九页,共三十九页。Get操作142564375575644321heappa第二十页,共三十九页。functionget:longint;varpa,son,tmp:longint;beginget:=heap[1];heap[1]:=heap[len];len:=len-1;pa:=1;whilepa*2<=lendobeginif(pa*2+1>len)or(heap[pa*2]heap[son]thenbegintmp:=heap[pa];heap[pa]:=heap[son];heap[son]:=tmp;pa:=son;endelsebreak;end;end;第二十一页,共三十九页。intget(){intp=heap[1],pa=1,son,tmp;heap[1]=heap[len];len--;while(pa*2<=len){if(pa*2+1>len||heap[pa*2]heap[son]){tmp=heap[pa];heap[pa]=heap[son];heap[son]=tmp;pa=son;}elsereturnp;}returnp;}第二十二页,共三十九页。建立堆•方法一:对数组中的每个数依次进行插入操作;Pascal:fori:=1tondoread(a[i]);fori:=1tondoput(a[i]);C++:for(inti=1;i<=n;i++)cin>>a[i];for(inti=1;i<=n;i++)put(a[i]);•方法二:直接对数组a进行调整,从a[ndiv2]开始向下调整成堆,然后对a[ndiv2-1]调整,直至a[1]。第二十三页,共三十九页。堆的应用例1、堆排序假设n个随机整数存放在A[1..n]中,我们可以利用堆将它们从小到大进行排序,这种排序方法,称为“堆排序”。【问题分析】(1)建立小根堆(2)取出根结点并调整堆:将根结点输出,并与小根堆的最后一个结点交换,再从上到下进行调整,使其仍为小根堆,重复(2)操作...