NOIP普及讲座8-堆及其应用VIP专享VIP免费

堆及其应用江苏省华罗庚中学杨志军第一页，共三十九页。堆的定义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)操作...