网站开发 与 网页设计的区别,计算机前端和后端区别,wordpress 缓存文件夹,德国设计网站大全一、定义最小-最大堆#xff1a;各层交替为最小层和最大层的堆。最大层#xff1a;该层上的节点大于等于以其为根节点的子树上的所有节点。最小层#xff1a;该层上的节点小于等于以其为根节点的子树上的所有节点。本文中#xff0c;我们令堆的层数从1开始#xff0c;节点…一、定义最小-最大堆各层交替为最小层和最大层的堆。最大层该层上的节点大于等于以其为根节点的子树上的所有节点。最小层该层上的节点小于等于以其为根节点的子树上的所有节点。本文中我们令堆的层数从1开始节点编号也从1开始即根节点为第1层编号为1。最小最大对具有如下性质对于任一节点从该节点到叶节点的任意一条路径(1)处于最小层的节点关键字逐渐增大(2)处于最大层的节点关键字逐渐减小(3)所有处于最大层的节点关键字大于所有处于最小层的节点的关键字。证明假设取这样一条路径上面的节点依次为x1、x2、x3、…、xn。假设x1处于最小层则所有处于最小层的元素为x3、x5等所有处于最大层的元素为x2、x4等。(1) 由于x3处于以x1为根的树上且x1处于最小层因此x1小于x3同理x5处于以x3为根的树上且x3处于最小层因此x3小于x5等依次类推所有处于最小层的元素逐渐增大(2) 因为x4处于以x2为根的树上且x2处于最大层因此x2大于x4依次类推所有处于最大层的元素依次减小(3) 假设最小层最后一个节点是xs最大层最后一个节点为xt因为不可能连续两层或两层以上是最大层或最小层因此xs与xt必然处于相邻的两层且xs小于xt(假设xs是xt的父节点因为xs是最小层而xt处于以xs为根的子树上因此xs小于xt假设xs是xt的子节点因为xt是最大层而xs处于以xt为根的子树上因此xs小于xt因此不管xs和xt谁是父节点都有xs小于xt)。由前面可知xs是x1、x3、…、xs等节点的最大值xt是x2、x4、…、xt等节点的最小值前一序列的最大值小于后一序列的最小值因此前一序列的所有值小于后一序列的所有值。证明结束。推论假设最小-最大堆中有n个节点其中最小层节点数为ms最大层节点数为mt则最小层节点必是n个节点中最小的ms个节点最大层节点必是n个节点中最大的mt个节点。二、最小-最大堆的插入具体实现见下面我们使用min_max_insert将item插入到堆heap中插入前节点个数为*n。边界条件不进行详细解释。首先将item存入heap[*n1]处检查该元素的父节点是最大层还是最小层。1)父节点是最小层且该元素小于父节点该节点是最后一个节点且处于最大层本次插入只增加最大层节点数最小层节点数不变父节点是最小层的最后一个元素是最小层节点中最大的节点假设插入前最小层节点数为ms最大层节点数为mt则插入后最小层节点数不变最小层节点数为mt1。由推论可知最小层节点是所有节点中最小的前ms个节点父节点属于这ms个节点中最大的节点现在新插入的节点小于父节点就意味着新节点将代替父节点成为最小的前ms个节点之一因此父节点属于最大层节点。又由于父节点原先小于最小层因此小于所有原先最大层的节点现在转入最大层后成为最大层节点中最小的节点根据最小最大堆的性质可知父节点必属于其所属路径上的最后一个节点。因此我们直接把父节点放入heap[*n1]处即可。对于新加入节点我们不需要改动其它路径只需沿着heap[*n1]到根节点的这条路径找出所有最小层节点将其放在某位置使得该路径上节点顺序满足最小最大堆性质(1)即可。2)父节点是最小层且该元素大于父节点同理新加入节点只是改变了最大层节点数不会改变最小层节点数。父节点是前ms个最小节点中最大的新节点大于父节点所以新节点不可能是前ms个最小节点所以新节点属于最大层。因此我们只需找出heap[*n1]到根节点的这条路径上所有最大层节点将新节点放入某个位置其它节点依次后移使得这些节点满足最小最大堆的性质(2).3)父节点是最大层且该元素大于父节点此时新加入的节点处于最小层所以新节点的加入改变的是最小层节点数不会改变最大层节点数。最大层节点是所有节点中最大的mt个节点且父节点是则mt个节点中最小的节点新节点大于父节点就意味着父节点不可能再成为最大的前mt个节点所以新节点代替父节点成为最大层节点。由于父节点大于所有最小层节点所以父节点应该是出于该路径上的最后一个位置因此直接将父节点放入heap[*n1]即可。对于新节点只需找出heap[*n1]到根节点路径上的所有最大层节点将新节点放入某位置其它节点依次后移使得该路径上所有最小层节点满足性质(1)即可。4)父节点是最大层且该元素小于父节点最大层节点不变仍是原先的mt个节点。新节点属于最小层节点将新节点加入heap[*n1]找出heap[*n1]到根节点路径上所有最小层节点重新排序满足性质(1)。三、最小-最大堆的删除(最小元素)基本思想最小元素就是最小-最大堆根节点对应的元素所以每次都是直接删除该节点。如果还有剩余节点接着要做的就是将剩余节点重新组织成一个新的最小-最大堆。最直接的方式就是对所有元素重新建堆即把剩余元素逐个输入堆里每输入一个元素调用一次函数min_max_insert将已输入元素建成最小-最大堆直到所有元素输入为止。但这么做显然效率是比较低的原先的堆里所包含的信息被全部丢弃。直觉告诉我们可以利用原先堆的信息找到更简便的方法。我们现在将剩余节点全部保留在原位置缺了一个根节点于是我们很自然的想到要找一个节点放入根节点位置我们找到剩余节点中最小的节点放入根节点。因为最小最大堆的根节点是整个堆中最小的元素所有首先在剩余节点中找到最小的节点并将该节点放入根节点处假设最小节点位置为k。现在k位置空了下来。另外现在堆节点数少了一个最后一个节点需要删除也就意味着该节点存放的元素将没有位置存放用item表示我们很自然地想到将item放在k位置。那么这么做究竟是否可行呢通过分析直接放在有些情况下会违反最小-最大堆下面我们具体分析(1)只剩一个节点不需进行任何操作(该节点已被放入根节点)(2)剩余两个或两个以上节点且k是最后一个节点不需进行任何操作(该节点已被放入根节点)(3)剩余两个或两个以上节点且k不是最后一个节点其它情况则需要根据k可能出现的位置来进一步分析首先k只可能出现在第二层或第三层(否则不可能是最小节点)。如果出现在第二层则有两种可能左儿子、右儿子。如果是左儿子说明左儿子没有子节点右儿子也没有子节点(完全二叉树)我们只需要将item直接放入k节点处即可如果是右儿子则右儿子没有子节点左儿子可能有子节点。不管左儿子有没有子节点都只需将item放入k节点即可如果出现在第三层不管最后一个节点是不是k节点的后代甚至不管k是否有后代将item放入k节点后都只会影响从根节点出发到到叶节点结束且经过k节点的路径其它路径仍满足最小最大堆的性质。我们由最小最大堆的性质和定义可知检查一个堆是否为最小最大堆只需检查其各条路径是否满足最小-最大堆性质即可。违反最小-最大堆有下面几种情况item大于k的父节点我们只需要item和父节点调换此时其它路径仍不会违反父节点仍是那些路径上的最大节点。接下来只需把item(此时已变为原先k的父节点元素)放入k节点但同样不能直接放入插入方式与最开始将最后一个元素插入根节点一样。因为此时k是第三层其父节点是第二层为最大层所以父节点应大于k节点父节点处于第二层大于以其为根的堆中所有元素。item既然大于父节点且即将成为这个堆中的元素之一因此item是新堆中最大的元素应将其放在父节点的位置且不管后面如何排都不会改变也就是说我们接下来只需考虑以k节点及k节点的兄弟为根的子树。另外以k节点的兄弟为根的子树在父节点和item交换后并不违反最小-最大堆性质因此我们只需考虑以k为根的子树。问题就变成了将新的item插入以k为根的子树的根节点(即k节点)。这和最先将最后一个元素插入根节点完全相同。item大于k的子节点把item插入k节点插入方式与最开始将最后一个元素插入根节点一样。通过上面的分析item插入以k的父节点为根的堆中后堆的最大元素仍然是k的父节点所以父节点不变因此k的兄弟节点所在的路径或子堆也未违反最小-最大堆性质不需改变所以我们就只考虑将item插入以k为根的堆中的根节点(即k节点)即可。总结起来就是三种情况a)k处于第二层b)k处于第三层且item大于k的父节点c)k处于第三层且item大于k的子节点结合边界条件我们很容易进行实现。四、C语言实现#include#include#define MAX_SIZE 100#define FALSE 0#define TRUE1#define SWAP(x,y,t)((t)(x),(x)(y),(y)(t))typedef struct{int key;}element;element heap[MAX_SIZE];void min_max_insert(element heap[], int *n,element item);int level(int n);void verify_min(element heap[], int n);void verify_max(element heap[], int n);element delete_min(element heap[], int*n);int find_min(element heap[] ,int n1,intn2);void show(element heap[],int n);int main(void){int n0;int i,j;elementrr[23]{{7},{3},{70},{20},{40},{80},{30},{5},{9},{17},{10},{100},{15},{3},{45},{0},{50},{2},{30},{88},{20},{99},{12}};for(i0;i23;i)min_max_insert(heap,n, arr[i]);show(heap,n);element temp;for(i0;i23;i){tempdelete_min(heap,n);printf(the deleted element is %d\n,temp.key);}system(PAUSE);return 0;}element delete_min(element heap[], int*n){heap[0]heap[1];//heap[0]保存要删除的元素if((*n)1){(*n)--;return heap[0];}int parent,last,i,k;element temp,st;tempheap[(*n)--];for(i1,last(*n)/2;ilast;){kfind_min(heap,i,*n);if(temp.keyheap[k].key)break;heap[i]heap[k];if(k2*i1){ik;break;}parentk/2;if(heap[parent].keySWAP(heap[parent],temp,st);ik;}heap[i]temp;return heap[0];}void show(element heap[],int n){int j;printf(The heap is:\n);for(j1;jn;j)printf(%d,heap[j].key);printf(\n);}int find_min(element heap[] ,int n1,intn2)//在堆中寻找n1节点的后代中最小的节点注意并不是heap中所有位于n1后面的节点都是n1节点的后代{if(n1n2){fprintf(stderr,n1 must be smaller than n2);exit(1);}int i,j,k;k2*n1;for(i1,jpow(2,i)*n1;jn2;){if(heap[j].keykj;if(jpow(2,i)*(n11)-1){i;jpow(2,i)*n1;}elsej;}return k;}void min_max_insert(element heap[], int *n,element item){(*n);if (*nMAX_SIZE){fprintf(stderr,The heap is full.\n);exit(1);}int parent(*n)/2; //父节点下标element temp;if (parent0) //说明*n1即当前插入的item是heap中的第一个元素heap[1]item;else{heap[*n]item; //先把item放在最后一个位置switch(level(parent)){case FALSE:if(heap[*n].key{SWAP(heap[*n],heap[parent],temp);verify_min(heap,parent);break;}else{verify_max(heap,*n);break;}case TRUE:if(heap[*n].keyheap[parent].key){SWAP(heap[*n],heap[parent],temp);verify_max(heap,parent);}elseverify_min(heap,*n);default:break;}}}int level(int n){int ilog2(n);if(i%2)//maxreturn1;return0;}void verify_min(element heap[], int n){if (n1){int parent(n/2);parentparent/2;if(parent)if(heap[n].key{element temp;SWAP(heap[n],heap[parent],temp);verify_min(heap,parent);}}}void verify_max(element heap[], int n){if (n1){int parent(n/2);parentparent/2;//父节点的父节点if(parent)if(heap[n].keyheap[parent].key){element temp;SWAP(heap[n],heap[parent],temp);verify_min(heap,parent);}}}运行结果099 100210153403050 8880703045573 920201712thedeleted element is 0thedeleted element is 2thedeleted element is 3thedeleted element is 3thedeleted element is 5thedeleted element is 7thedeleted element is 9thedeleted element is 10thedeleted element is 12thedeleted element is 15thedeleted element is 17thedeleted element is 20thedeleted element is 20thedeleted element is 30thedeleted element is 30thedeleted element is 40thedeleted element is 45thedeleted element is 50thedeleted element is 70thedeleted element is 80thedeleted element is 88thedeleted element is 99thedeleted element is 100
