NOIP普及讲座8-堆及其应用课件.ppt

《NOIP普及讲座8-堆及其应用课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、堆及其应用江苏省华罗庚中学杨志军堆的定义01堆的性质02堆的基本操作03堆的应用04TableofContents内容大纲预备知识完全二叉树：如果一棵深度为K的二叉树，1至K-1层的结点都是满的，即满足2i-1(1<=i<=k-1),只有最下面的一层的结点数小于等于2k-1，并且最下面一层的结点都集中在该层最左边的若干位置，则此二叉树称为完全二叉树。预备知识1234567满二叉树12345完全二叉树堆的定义堆也称二叉堆，结构上是一种数组，本质上是一棵完全二叉树。树中每个结点与数组中存放该结点中值的那个元素相对应。堆的性质树根

2、为A[1]，利用完全二叉树的性质，可以求出第i个结点的父结点、左孩子结点、右孩子结点的下标分别为：trunc(i/2)、2i、2i+1。堆的性质二叉堆还具有这样一个重要的性质：对除根以外的每个结点i，A[parent(i)]≥A[i]，即所有结点的值都不得超过其父结点的值，称为大根堆。小根堆就是要求：A[parent(i)]≤A[i]。堆的基本操作使用堆的关键部分是两个基本操作：Put操作：即往堆中加入一个结点。方法是往堆尾加入一个结点，并通过从下往上的调整法，使其继续保持堆的性质；Get操作：即从堆中取出根结点。方法是从堆

3、中取出堆头结点，并删除该结点(堆尾覆盖)，再通过从上往下的调整法，使其继续保持堆的性质；Put操作575644321142564375heapPut操作14256437557561443211425643751heapPut操作14256437515756144321heap1425143756sonPut操作14251437565751644321heap1125443756sonPut操作11254437565754614321heapsonPut操作procedureput(x:longint);varfa,son,t

4、mp: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]>h

5、eap[son]){tmp=heap[son/2];heap[son/2]=heap[son];heap[son]=tmp;son=son/2;}}Get操作11254437565754614321heapGet操作11254437565754614321heap612544375Get操作612544375575414326heap162544375paGet操作162544375575464321heap142564375paGet操作142564375575644321heappafunctionget:longint

6、;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;endelsebrea

7、k;end;end;intget(){intp=heap[1],pa=1,son,tmp;heap[1]=heap[len];len--;while(pa*2<=len){if(pa*2+1>len

8、

9、heap[pa*2]heap[son]){tmp=heap[pa];heap[pa]=heap[son];heap[son]=tmp;pa=son;}elsereturnp;}returnp;}建立堆方法一：对数组中的每个数依次

10、进行插入操作;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[ndiv