数据结构之树形结构2-堆课件

堆数据结构之树形结构堆数据结构之树形结构11.什么是树？

复习1.什么是树？

复习2树

树是由n(n>=0)个节点构成集合。特点是任何两个节点间有且仅有一条路径。ABCDEGHFLJK根节点：没有父亲的节点。一棵树只有一个根节点。EKJA每个节点可有0个或多个儿子节点除根节点外，每个结点有且只有一个父亲节点J和K是E的儿子节点

E是J和K的父亲节点A是E的父节点没有儿子的节点称为叶节点，比如F

G

H

L

J

K都是叶节点父亲相同的节点称为兄弟节点，比如FGH是兄弟节点的儿子的个数称为节点的度，比如A的度数为4祖先、子孙包含一个节点的所有子孙和该节点本身的集合，称为子树复习树树是由n(n>=0)个节点构成集合。特点是任何31.什么是树？

2.什么是二叉树？

复习1.什么是树？

2.什么是二叉树？

复习41.什么是树？

2.什么是二叉树？

3.二叉树第i层最多有多少个节点？

复习1.什么是树？

2.什么是二叉树？

3.二叉树第i层最多有多51.什么是树？

2.什么是二叉树？

3.二叉树第i层最多有多少个节点？

4.高度为h的二叉树最多有多少个节点？

复习1.什么是树？

2.什么是二叉树？

3.二叉树第i层最多有多61.什么是树？

2.什么是二叉树？

3.二叉树第i层最多有多少个节点？

4.高度为h的二叉树最多有多少个节点？

5.二叉树叶节点和度为2的节点的关系是？

复习1.什么是树？

2.什么是二叉树？

3.二叉树第i层最多有多7二叉树（Binarytree）二叉树就是每个节点最多只有两个子节点的树。二叉树的特点：1.第i层上最多有个节点2.高度为h的二叉树最多有个节点2i-12h-13.在非空二叉树中，叶节点的个数等于度为2的节点个数加1ABCGFJKLM复习二叉树（Binarytree）二叉树就是每个节点最多只有两8

6.什么是完全二叉树？什么是满二叉树？

复习

6.什么是完全二叉树？什么是满二叉树？

复习9二叉树每层节点数都达到最大的二叉树树叫满二叉树ABCGFJK满二叉树除最底层外，其余各层节点都达到最大值，且最底层的节点集中在左侧的连续位置上的二叉树叫完全二叉树。ABCGFK完全二叉树复习二叉树每层节点数都达到最大的二叉树树叫满二叉树ABCGFJK101835627写出前序，中序，后续遍历序列前顺：1,8,5,3,6,7,2中序：8,5,1,7,6,2,3后续：5,8,7,2,6,3,1复习1835627写出前序，中序，后续遍历序列前顺：1,8,5,11二叉堆(heap)二叉堆是完全二叉树任何一个节点都大于他的儿子节点的值(大根堆)

或者任何一个节点都小于他的儿子节点的值(小根堆)父>子，则堆顶元素值一定最大父<子，则堆顶元素值一定最小98716253二叉堆(heap)二叉堆是完全二叉树9871625312#defineMaxn堆的最大元素个数//#definemaxn11intheap[Maxn],n;//整型数组heap来存储堆，n表示堆的结点总数规定这种存储结构中：heap[1]是堆的根；结点heap[i]的父亲是heap[i/2]（i>1）//比如5号节点的父亲是2号节点结点heap[i]左孩子是heap[2*i]，右孩子是heap[2*i+1]i<=n/2根据堆的定义可以知道：对于大根堆：heap[1]最大heap[i]≥h[2*i]且heap[i]≥heap[2*i＋１]（1≤i≤n/2）大根堆heap数组下标堆用一维数组来存储，父子关系可通过数组下标快速计算出来#defineMaxn堆的最大元素个数//#defi13已知下列数组表示一个堆，请画出这个堆！12382772664945下标123456781234567998定理：堆的高度最大为log2(n+1)因为高度为h的二叉树最多有2h-1个节点。2h-1=n那么h=log2(n+1)已知下列数组表示一个堆，请画出这个堆！1238277266414怎样建堆？(小根)3建堆开始……65742313877152163613建堆完毕……数组heap初始时n=11数组下标从第下标为n/2的节点开始，依次讨论下标为n/2+1,n/2+2,...,2,1建堆的时间复杂度为O(n)详细证明见《算法导论》第77页，或者《算法分析与设计》第74页数组heap建堆完毕后1234567891011怎样建堆？(小根)3建堆开始……6574231387715215堆的向下调整(小根)voidshift(inti,intn)

{

intk,t;

t=heap[i];

k=2*i;

while(k<=n)

{

if((k<n)&&(heap[k]>heap[k+1]))k++;

if(t>heap[k]){heap[i]=heap[k];

i=k;k=2*i;}

elsebreak;

}

heap[i]=t;

}//把以i号节点(下标为i)为根的子树调整为堆，n为堆最后一个节点的下标(也就是数组的长度)//k表示当前节点孩子的下标//找出值最小的孩子的下标//把值最小的孩子的值赋值给根//结束循环//把根的值赋值交换给孩子#definemaxn1000

int

heap[maxn];堆的向下调整(小根)voidshift(inti,int16voidshift(inti,intn)

{

intk,t;

t=heap[i];

k=2*i;

while(k<=n)

{

if((k<m)&&(heap[k]>heap[k+1]))k++;

if(t>heap[k]){heap[i]=heap[k];

i=k;k=2*i;}

elsebreak;

}

heap[i]=t;

}365523138771521636131234567891011voidshift(inti,intn)

{

17堆的向下调整(小根)voidshift(inti,intn)

{

intk,t;

t=heap[i];

k=2*i;

while(k<=n)

{

if((k<n)&&(heap[k]>heap[k+1]))k++;

if(t>heap[k]){heap[i]=heap[k];

i=k;k=2*i;}

elsebreak;

}

heap[i]=t;

}//把以i号节点(下标为i)为根的子树调整为堆，n为堆最后一个节点的下标(也就是数组的长度)//k表示当前节点孩子的下标//找出值最小的孩子的下标//把值最小的孩子的值赋值给根//结束循环//把根的值赋值交换给孩子#definemaxn1000

int

heap[maxn];建堆：for(i=n/2;i>=1;i--)shift(i,n);调整一次堆的时间复杂度在最坏情况下是O(log2n)堆的向下调整(小根)voidshift(inti,int18堆排序堆排序的基础——选择排序堆排序的实质是利用二叉堆优化选择排序堆排序步骤：建堆。将所有节点布置成堆结构取出堆顶节点把堆尾的节点移动至顶部，调整此堆跳转至2步骤，直至堆为空堆排序堆排序的基础——选择排序19堆排序——选择与维出堆顶节点71273728833868一、取出cout<<heap[1];heap[1]=heap[n];n--;二、向下调整shift(1,n)堆排序——选择与维出堆顶节点71220while(n>0)

{

cout<<heap[1];

heap[1]=heap[n--];

shift(1,n);

}排序while(n>0)

{

cout<<heap[1]21intheap[100],t,j,n;voidshift(inti,intn){intk,t;

t=heap[i];

k=2*i;

while(k<=n)

{

if((k<n)&&(heap[k]>heap[k+1]))k++;

if(t>heap[k]){heap[i]=heap[k];i=k;k=2*i;}elsebreak;

}

heap[i]=t;}intmain()

{

cin>>n;for(j=1;j<=n;j++)

cin>>heap[

j];

for(j=n/2;

j>=1;j--)shift(j,n);

while(n>0)

{

cout<<heap[1];

heap[1]=heap[n--];

shift(1,n);

}return0;

}intheap[100],t,j,n;intmain(22例：NK宇宙班题目描述：CQNK中学高一年级总共有n(n<=500000)个学生。现在你有他们的“星际语”成绩单，要从中找出“星际语”成绩最好的m(m<=1000并且m<n)个学生组成宇宙班，请按由高到低的顺序打印出加入于周班学生的“星际语”成绩。输入格式：第一行，两个整数n和m第二行，n个用空格间隔的整数，分别表示n个学生的“星际语”成绩输出格式：只有一行，m个空格间隔的整数，表示加入宇宙班学生的“星际语”成绩。样例输入：1258987779568561008065959971样例输出：10099959589例：NK宇宙班23直接对n个数由大到小排序，然后取最大的m个数取出来，时间复杂度：普通排序(冒泡、选择、插入)：O(n2+m)//一定超时快速排序:O(nlog2n+m)有没有更快的方法？1.把n个数字建成堆2.把堆顶节点的打印出来，删除堆顶元素，调整堆。第2步重复m次。O(n)O(log2n)O(mlog2n)总时间复杂度：O(n+mlog2n)n最大为500000，219=524288,也就是log2n的值不超过19直接对n个数由大到小排序，然后取最大的m个数取出来，有没有更24#definemaxn500001usingnamespacestd;intheap[maxn],n,m;voidshift(inti,intlen)

//调整成大根堆{

intt=heap[i],k=2*i;

while(k<=len)

{

if((k<len)&&(heap[k]<heap[k+1]))k++;

//k记录值最大的孩子的编号（大根堆）

if(t<heap[k]){

heap[i]=heap[k];

i=k;

k=2*i;

}

elsebreak;

}

heap[i]=t;}intmain(){

inti;

scanf("%d%d",&n,&m);

for(i=1;i<=n;i++)scanf("%d",&heap[i]);

//建堆

for(i=n/2;i>=1;i--)shift(i,n);

//选出最大的m个数字

for(i=1;i<=m;i++)

{

printf("%d",heap[1]);

//打印堆顶元素的值，即取出最大元素

heap[1]=heap[n];

//把最后一个节点移到堆顶，相当于把原来堆顶节点删了

n--;

//删除堆顶节点后，总节点数减1

shift(1,n);

//重新调整堆，把剩余节点中最大的值调到堆顶

}

return0;}#definemaxn50000125堆的操作堆的操作26//堆的向下调整voidShiftDown(inti,intn){intk,t;t=heap[i];k=2*i;while(k<=n){if((k<n)&&(heap[k]>heap[k+1]))k++;if(t>heap[k]){heap[i]=heap[k];i=k;k=2*i;}elsebreak;}heap[i]=t;}//堆的向下调整27//删除堆顶元素voidDel(){Heap[1]=Heap[n];n--;if(n>0)ShiftDown(1,n);}//删除堆顶元素28//添加值为x的元素voidInsert(intx){n++;Heap[n]=x;//将新元素添加在末尾

ShiftUp(n);//向上调整堆}//添加值为x的元素29//堆的向下调整voidShiftDown(intx,intn)//从编号为x的元素往下调整为小根堆{intk,t;t=heap[x];k=2*x;while(k<=n){if((k<n)&&(heap[k]>heap[k+1]))k++;if(t>heap[k]){heap[x]=heap[k];x=k;k=2*x;}elsebreak;}heap[x]=t;}//堆的向上调整voidShiftUp(intx)

//从编号为x的元素往上调整为小根堆{intt=Heap[x],k=x/2;while(k>0){if(t<Heap[k]){Heap[x]=Heap[k];x=k;k=k/2;}elsebreak;}Heap[x]=t;}//堆的向下调整//堆的向上调整30特点：不稳定时间复杂度最坏情况下不超过

o(nlog2n)特点：不稳定31课后练手：何老板捡钻石题目描述：“欢迎来安哥拉观光，运气好能捡到钻石，运气不好就踩中地雷"，看了这则旅游广告，何老板决定去安哥拉碰碰运气。到了安哥拉才发现有个坑爹的规定：游客最多只能带走n颗钻石，否则就视为走私。何老板运气很好，他很快就搜集齐了n颗钻石，他把它们编号1到n放进了箱子。在回机场的路上，何老板发现路边还可以零星的捡到一些钻石。沿路何老板总共发现了m颗钻石，他把它们编号为n+1到n+m。何老板是个聪明人，他只会带走较重的钻石，如果捡起的钻石比箱子里的都要轻，何老板就直接把它扔掉，否则他就把箱子中最轻的钻石扔了，把新捡的放进箱子。请问何老板沿途把哪些钻石从箱子里扔了出去，请按先后顺序打印出被扔出的钻石的编号。（假定每颗钻石的重量都不同，不超过int范围）。输入格式：第一行，两个空格间隔的整数n和m，(n<=20000,m<=100000)第二行，n个空格间隔的整数，表示已装到箱子中的n颗钻石的重量第三行，m个空格间隔的整数，表示沿途捡到的m颗钻石的重量输出格式：只有一行：若干个空格间隔的整数，表示从箱子里扔出的钻石的编号样例输入：5585937421158样例输出：462课后练手：何老板捡钻石32intmain()......scanf("%d%d",&n,&m);for(i=1;i<=n+m;i++){

scanf("%d",&heap[i]);

number[i]=i;

}for(i=n/2;i>=1;i--)ShiftDown(i,n);x=n+m;for(i=n+1;i<=n+m;i++){

if(heap[i]>heap[1])

{

printf("%d",number[1]);

heap[1]=heap[i];

number[1]=number[i];

ShiftDown(1,n);

}}.......intmain()33voidShiftDown(inti,intn)......t=heap[i];

y=number[i];

k=i*2;while(k<=n){

if((k<n)&&(heap[k]>heap[k+1]))k++;

if(t>heap[k])

{

heap[i]=heap[k];number[i]=number[k];

i=k;

k=2*i;

}

elsebreak;}heap[i]=t;

number[i]=y;......voidShiftDown(inti,intn)34课后作业：1821

对于一给定的素数集合S={p1,p2,...,pK},考虑一个正整数集合，该集合中任一元素的质因数全部属于S。这个正整数集合包括，p1、p1*p2、p1*p1、p1*p2*p3...(还有其它)。该集合被称为S集合的“丑数集合”。

对于输入的集合S去寻找“丑数集合”中的第N小的“丑数”。样例：419//求第19个丑数2357//给定的S集合结果：2

3

4

5

6

7

8

9

10

12

14

15

16

18

20

21

24

25

27课后作业：1821对于一给定的素数集合S=35以样例数据（2357）为例：★初始：建立一个小根堆，把数字1放入堆中；★每次从堆中取出堆顶元素k，再把2k,3k,5k,7k放入堆中；★从2开始，取出的第n个元素就是第n小的丑数；★每取出一个数，插入4个数，因此任何堆里的元素是O(n)的，时间复杂度为O(4nlogn)上述解法有没有问题呢？产生了相同的数字怎么处理？比如2*3,和3*2以样例数据（2357）为例：上述解法有没有问题呢？36main()...... longlongi,k,x,m,tmp,cnt=0; scanf("%I64d%I64d",&k,&m); for(i=1;i<=k;i++)scanf("%I64d",&a[i]); heap[1]=tmp=1;n=1;

//数字1进堆，n记录堆中数字个数 while(cnt<m)

//cnt记录产生的丑数的个数

{ tmp=heap[1];

//tmp用于判重，记录当前取出的堆顶元素 Del();cnt++; for(i=1;i<=k;i++) { x=tmp*a[i]; if(x<=inf)Insert(x);

//inf=2^31题目说答案在int范围内 } while(heap[1]==tmp)Del();

//若现在的堆顶元素与刚取出的相同，则跳过。

}

printf("%I64d\n",heap[1]);main()37课后作业：2280课后作业：228038堆数据结构之树形结构堆数据结构之树形结构391.什么是树？

复习1.什么是树？

复习40树

树是由n(n>=0)个节点构成集合。特点是任何两个节点间有且仅有一条路径。ABCDEGHFLJK根节点：没有父亲的节点。一棵树只有一个根节点。EKJA每个节点可有0个或多个儿子节点除根节点外，每个结点有且只有一个父亲节点J和K是E的儿子节点

E是J和K的父亲节点A是E的父节点没有儿子的节点称为叶节点，比如F

G

H

L

J

K都是叶节点父亲相同的节点称为兄弟节点，比如FGH是兄弟节点的儿子的个数称为节点的度，比如A的度数为4祖先、子孙包含一个节点的所有子孙和该节点本身的集合，称为子树复习树树是由n(n>=0)个节点构成集合。特点是任何411.什么是树？

2.什么是二叉树？

复习1.什么是树？

2.什么是二叉树？

复习421.什么是树？

2.什么是二叉树？

3.二叉树第i层最多有多少个节点？

复习1.什么是树？

2.什么是二叉树？

3.二叉树第i层最多有多431.什么是树？

2.什么是二叉树？

3.二叉树第i层最多有多少个节点？

4.高度为h的二叉树最多有多少个节点？

复习1.什么是树？

2.什么是二叉树？

3.二叉树第i层最多有多441.什么是树？

2.什么是二叉树？

3.二叉树第i层最多有多少个节点？

4.高度为h的二叉树最多有多少个节点？

5.二叉树叶节点和度为2的节点的关系是？

复习1.什么是树？

2.什么是二叉树？

3.二叉树第i层最多有多45二叉树（Binarytree）二叉树就是每个节点最多只有两个子节点的树。二叉树的特点：1.第i层上最多有个节点2.高度为h的二叉树最多有个节点2i-12h-13.在非空二叉树中，叶节点的个数等于度为2的节点个数加1ABCGFJKLM复习二叉树（Binarytree）二叉树就是每个节点最多只有两46

6.什么是完全二叉树？什么是满二叉树？

复习

6.什么是完全二叉树？什么是满二叉树？

复习47二叉树每层节点数都达到最大的二叉树树叫满二叉树ABCGFJK满二叉树除最底层外，其余各层节点都达到最大值，且最底层的节点集中在左侧的连续位置上的二叉树叫完全二叉树。ABCGFK完全二叉树复习二叉树每层节点数都达到最大的二叉树树叫满二叉树ABCGFJK481835627写出前序，中序，后续遍历序列前顺：1,8,5,3,6,7,2中序：8,5,1,7,6,2,3后续：5,8,7,2,6,3,1复习1835627写出前序，中序，后续遍历序列前顺：1,8,5,49二叉堆(heap)二叉堆是完全二叉树任何一个节点都大于他的儿子节点的值(大根堆)

或者任何一个节点都小于他的儿子节点的值(小根堆)父>子，则堆顶元素值一定最大父<子，则堆顶元素值一定最小98716253二叉堆(heap)二叉堆是完全二叉树9871625350#defineMaxn堆的最大元素个数//#definemaxn11intheap[Maxn],n;//整型数组heap来存储堆，n表示堆的结点总数规定这种存储结构中：heap[1]是堆的根；结点heap[i]的父亲是heap[i/2]（i>1）//比如5号节点的父亲是2号节点结点heap[i]左孩子是heap[2*i]，右孩子是heap[2*i+1]i<=n/2根据堆的定义可以知道：对于大根堆：heap[1]最大heap[i]≥h[2*i]且heap[i]≥heap[2*i＋１]（1≤i≤n/2）大根堆heap数组下标堆用一维数组来存储，父子关系可通过数组下标快速计算出来#defineMaxn堆的最大元素个数//#defi51已知下列数组表示一个堆，请画出这个堆！12382772664945下标123456781234567998定理：堆的高度最大为log2(n+1)因为高度为h的二叉树最多有2h-1个节点。2h-1=n那么h=log2(n+1)已知下列数组表示一个堆，请画出这个堆！1238277266452怎样建堆？(小根)3建堆开始……65742313877152163613建堆完毕……数组heap初始时n=11数组下标从第下标为n/2的节点开始，依次讨论下标为n/2+1,n/2+2,...,2,1建堆的时间复杂度为O(n)详细证明见《算法导论》第77页，或者《算法分析与设计》第74页数组heap建堆完毕后1234567891011怎样建堆？(小根)3建堆开始……6574231387715253堆的向下调整(小根)voidshift(inti,intn)

{

intk,t;

t=heap[i];

k=2*i;

while(k<=n)

{

if((k<n)&&(heap[k]>heap[k+1]))k++;

if(t>heap[k]){heap[i]=heap[k];

i=k;k=2*i;}

elsebreak;

}

heap[i]=t;

}//把以i号节点(下标为i)为根的子树调整为堆，n为堆最后一个节点的下标(也就是数组的长度)//k表示当前节点孩子的下标//找出值最小的孩子的下标//把值最小的孩子的值赋值给根//结束循环//把根的值赋值交换给孩子#definemaxn1000

int

heap[maxn];堆的向下调整(小根)voidshift(inti,int54voidshift(inti,intn)

{

intk,t;

t=heap[i];

k=2*i;

while(k<=n)

{

if((k<m)&&(heap[k]>heap[k+1]))k++;

if(t>heap[k]){heap[i]=heap[k];

i=k;k=2*i;}

elsebreak;

}

heap[i]=t;

}365523138771521636131234567891011voidshift(inti,intn)

{

55堆的向下调整(小根)voidshift(inti,intn)

{

intk,t;

t=heap[i];

k=2*i;

while(k<=n)

{

if((k<n)&&(heap[k]>heap[k+1]))k++;

if(t>heap[k]){heap[i]=heap[k];

i=k;k=2*i;}

elsebreak;

}

heap[i]=t;

}//把以i号节点(下标为i)为根的子树调整为堆，n为堆最后一个节点的下标(也就是数组的长度)//k表示当前节点孩子的下标//找出值最小的孩子的下标//把值最小的孩子的值赋值给根//结束循环//把根的值赋值交换给孩子#definemaxn1000

int

heap[maxn];建堆：for(i=n/2;i>=1;i--)shift(i,n);调整一次堆的时间复杂度在最坏情况下是O(log2n)堆的向下调整(小根)voidshift(inti,int56堆排序堆排序的基础——选择排序堆排序的实质是利用二叉堆优化选择排序堆排序步骤：建堆。将所有节点布置成堆结构取出堆顶节点把堆尾的节点移动至顶部，调整此堆跳转至2步骤，直至堆为空堆排序堆排序的基础——选择排序57堆排序——选择与维出堆顶节点71273728833868一、取出cout<<heap[1];heap[1]=heap[n];n--;二、向下调整shift(1,n)堆排序——选择与维出堆顶节点71258while(n>0)

{

cout<<heap[1];

heap[1]=heap[n--];

shift(1,n);

}排序while(n>0)

{

cout<<heap[1]59intheap[100],t,j,n;voidshift(inti,intn){intk,t;

t=heap[i];

k=2*i;

while(k<=n)

{

if((k<n)&&(heap[k]>heap[k+1]))k++;

if(t>heap[k]){heap[i]=heap[k];i=k;k=2*i;}elsebreak;

}

heap[i]=t;}intmain()

{

cin>>n;for(j=1;j<=n;j++)

cin>>heap[

j];

for(j=n/2;

j>=1;j--)shift(j,n);

while(n>0)

{

cout<<heap[1];

heap[1]=heap[n--];

shift(1,n);

}return0;

}intheap[100],t,j,n;intmain(60例：NK宇宙班题目描述：CQNK中学高一年级总共有n(n<=500000)个学生。现在你有他们的“星际语”成绩单，要从中找出“星际语”成绩最好的m(m<=1000并且m<n)个学生组成宇宙班，请按由高到低的顺序打印出加入于周班学生的“星际语”成绩。输入格式：第一行，两个整数n和m第二行，n个用空格间隔的整数，分别表示n个学生的“星际语”成绩输出格式：只有一行，m个空格间隔的整数，表示加入宇宙班学生的“星际语”成绩。样例输入：1258987779568561008065959971样例输出：10099959589例：NK宇宙班61直接对n个数由大到小排序，然后取最大的m个数取出来，时间复杂度：普通排序(冒泡、选择、插入)：O(n2+m)//一定超时快速排序:O(nlog2n+m)有没有更快的方法？1.把n个数字建成堆2.把堆顶节点的打印出来，删除堆顶元素，调整堆。第2步重复m次。O(n)O(log2n)O(mlog2n)总时间复杂度：O(n+mlog2n)n最大为500000，219=524288,也就是log2n的值不超过19直接对n个数由大到小排序，然后取最大的m个数取出来，有没有更62#definemaxn500001usingnamespacestd;intheap[maxn],n,m;voidshift(inti,intlen)

//调整成大根堆{

intt=heap[i],k=2*i;

while(k<=len)

{

if((k<len)&&(heap[k]<heap[k+1]))k++;

//k记录值最大的孩子的编号（大根堆）

if(t<heap[k]){

heap[i]=heap[k];

i=k;

k=2*i;

}

elsebreak;

}

heap[i]=t;}intmain(){

inti;

scanf("%d%d",&n,&m);

for(i=1;i<=n;i++)scanf("%d",&heap[i]);

//建堆

for(i=n/2;i>=1;i--)shift(i,n);

//选出最大的m个数字

for(i=1;i<=m;i++)

{

printf("%d",heap[1]);

//打印堆顶元素的值，即取出最大元素

heap[1]=heap[n];

//把最后一个节点移到堆顶，相当于把原来堆顶节点删了

n--;

//删除堆顶节点后，总节点数减1

shift(1,n);

//重新调整堆，把剩余节点中最大的值调到堆顶

}

return0;}#definemaxn50000163堆的操作堆的操作64//堆的向下调整voidShiftDown(inti,intn){intk,t;t=heap[i];k=2*i;while(k<=n){if((k<n)&&(heap[k]>heap[k+1]))k++;if(t>heap[k]){heap[i]=heap[k];i=k;k=2*i;}elsebreak;}heap[i]=t;}//堆的向下调整65//删除堆顶元素voidDel(){Heap[1]=Heap[n];n--;if(n>0)ShiftDown(1,n);}//删除堆顶元素66//添加值为x的元素voidInsert(intx){n++;Heap[n]=x;//将新元素添加在末尾

ShiftUp(n);//向上调整堆}//添加值为x的元素67//堆的向下调整voidShiftDown(intx,intn)//从编号为x的元素往下调整为小根堆{intk,t;t=heap[x];k=2*x;while(k<=n){if((k<n)&&(heap[k]>heap[k+1]))k++;if(t>heap[k]){heap[x]=heap[k];x=k;k=2*x;}elsebreak;}heap[x]=t;}//堆的向上调整voidShiftUp(intx)

//从编号为x的元素往上调整为小根堆{intt=Heap[x],k=x/2;while(k>0){if(t<Heap[k]){Heap[x]=Heap[k];x=k;k=k/2;}elsebreak;}Heap[x]=t;}//堆的向下调整//堆的向上调整68特点：不稳定时间复杂度最坏情况下不超过

o(nlog2n)特点：不稳定69课后练手：何老板捡钻石题目描述：“欢迎来安哥拉观光，运气好能捡到钻石，运气不好就踩中地雷"，看了这则旅游广告，何老板决定去安哥拉碰碰运气。到了安哥拉才发现有个坑爹的规定：游客最多只能带走n颗钻石，否则就视为走私。何老板运气很好，他很快就搜集齐了n颗钻石，他把它们编号1到n放进了箱子。在回机场的路上，何老板发现路边还可以零星的捡到一些钻石。沿路何老板总共发现了m颗钻石，他把它们编号为n+1到n+m。何老板是个聪明人，他只会带走较重的钻石，如果捡起的钻石比箱子里的都要轻，何老板就直接把它扔掉，否则他就把箱子中最轻的钻石扔了，把新捡的放进箱子。请问何老板沿途把哪些钻石从箱子里扔了出去，请按先后顺序打印出被扔出的钻石的编号。（假定每颗钻石的重量都不同，不超过int范围）。输入格式：第一行，两个空格间隔的整数n和m，(n<=20000,m<=100000)第二行，n个空格间隔的整数，表示已装到箱子中的n颗钻石的重量第三行，m个空格间隔的整数，表示沿途捡到的m颗钻石的重量输出格式：只有一行：若干个空格间隔的整数，表示从箱子里扔出的钻石的编号样例输入：558