移动建站优化,网站开发与推广计划书,wordpress 插件 语言包,上海制作网页哪家好定义双端堆#xff1a;是一棵完全二叉树#xff0c;该完全二叉树要么为空#xff0c;要么同时满足下列性质#xff1a;(1) 根节点不包含元素#xff1b;(2) 左子树是一个最小堆#xff1b;(3) 右子树是一个最大堆#xff1b;(4) 如果右子树不空#xff0c;令i是左子树中…定义双端堆是一棵完全二叉树该完全二叉树要么为空要么同时满足下列性质(1) 根节点不包含元素(2) 左子树是一个最小堆(3) 右子树是一个最大堆(4) 如果右子树不空令i是左子树中任意一节点j是i在右子树中的对应节点。如果i在右子树中的对应节点不存在则令j为i父节点在右子树中的对应节点。对于节点i和j节点i的关键字小于等于j的关键字。 双端堆的插入操作步骤(1)若插入的新元素是在最小堆将新插入节点与其在最大堆中对应节点相比较如果大于对应节点则将两个节点元素互换对最大堆执行max_insert操作否则只需对最小堆执行min_insert操作。(2)若插入的新元素是在最大堆将新插入节点与其在最小堆中对应节点相比较如果小于对应节点则将两个节点元素互换对最小堆执行min_insert操作否则只需对最大堆执行max_insert操作。双端堆的删除操作以下以删除最小元素为例删除最大元素相似。删除最小元素基本思想首先将从最小堆的根节点删除的元素转换为从最小堆的叶子节点中删除元素的操作。这种转换是通过在沿根节点到叶子节点的路径上选择关键字值较小的节点逐步上移来完成的。其结果是把初始时位于最小堆根节点处的空位移到一个叶子节点p。然后用初始时位于双端堆最后位置的元素temp插入到该叶子节点p。插入操作类似双端堆的插入操作只是插入操作仅在最小堆中进行且其中max_paretner(i)的返回值j有改变。程序函数声明#ifndef HEAP_H_INCLUDED#define HEAP_H_INCLUDED#include#include#include#include#define MAX_SIZE 10int heap[MAX_SIZE];void deap_insert(int *heap,int *n,int item);//双端堆插入操作int delete_deap_min(int *heap,int *n);//删除双端堆的最小元素bool max_heap(int n);//判断节点是否在最大堆中int min_partner(int n);int max_partner(int n);void min_insert(int *heap,int n,int item);void max_insert(int *heap,int n,int item);void modified_deap_insert(int *heap,int i,int temp,int n);int modified_max_partner(int i,int n);#endif // HEAP_H_INCLUDED函数定义#includeHeap.h/*双端堆的插入操作*/void deap_insert(int *heap,int *n,int item){int i;(*n);if((*n)MAX_SIZE)//满堆{printf(The heap is full.\n);exit(1);}if(2(*n))//原来为空堆heap[2]item;else{bool flag;flagmax_heap(*n);//插入的节点是否在最大堆switch(flag){case true://节点在最大堆imin_partner(*n);//插入节点在最小堆所对应的节点if(item{heap[*n]heap[i];//交换元素min_insert(heap,i,item);//把数据item插入到最小堆中}elsemax_insert(heap,*n,item);//否则插入到最大堆中break;case false:imax_partner(*n);//插入节点在最大堆中对应的节点if(itemheap[i])//比较最大堆节点和插入元素的大小{heap[*n]heap[i];//交换元素max_insert(heap,i,item);//插入到最大堆中}elsemin_insert(heap,*n,item);//否则插入到最小堆break;}}}/*删除双端堆的最小元素操作*/int delete_deap_min(int *heap,int *n){int i,j;int temp;int item;if(*n2){fprintf(stderr,The heap is empty.\n);exit(1);}itemheap[2];//要删除的元素tempheap[(*n)--];//最后元素赋给temp;for(i2;2*i*n;){//将从最小堆根节点删除元素的操作//转换为从最小堆的叶子节点中删除元素的操作j2*i;//j为i的叶子节点if(j1*n){if(heap[j]heap[j1])j;//找出叶子节点中最小的关键字值节点}heap[i]heap[j];//将叶子节点上移ij;//其结果是把初始时位于根节点处的空位移动到叶子节点i;}modified_deap_insert(heap,i,temp,*n);//用初始时位于双端堆最后位置的节点元素插入到叶节点i;//该插入操作与deap_insert()的插入操作基本类似;只是插入操作仅在最小堆中;且其中max_partner(i)//的返回值j改变;return item;}/*判断节点n是否在最大堆中*/bool max_heap(int n){double a log(n)/log(2);double j n pow(2, (int)a-1);double b log(j)/log(2);if((int)a (int)b)return false;elsereturn true;}/*返回最大堆节点n对应最小堆的结点*/int min_partner(int n){double k log(n)/log(2);double a pow(2, (int)k-1);return n - (int)a;}/*返回最小堆节点n对应最大堆的结点*/int max_partner(int n){double k log(n)/log(2);double a pow(2, (int)k-1);return (n (int)a)/2;}/*最小堆的插入操作*/void min_insert(int *heap,int n,int item){int i,parent;in;parenti/2;while(parent1){if(heap[parent]item){heap[i]heap[parent];iparent;parent/2;}else break;}heap[i]item;}/*最大堆的插入操作*/void max_insert(int *heap,int n,int item){int i,parent;in;parenti/2;while(parent1){if(heap[parent]{heap[i]heap[parent];iparent;parent/2;}else break;}heap[i]item;}/*调整双端堆*/void modified_deap_insert(int *heap,int i,int temp,int n){int j;int itemtemp;i;if(iMAX_SIZE)//满堆{printf(The heap is full.\n);exit(1);}if(2i)//原来为空堆heap[2]item;else{bool flag;flagmax_heap(i);//插入的节点是否在最大堆switch(flag){case true://节点在最大堆jmin_partner(i);//插入节点在最小堆所对应的节点if(item{heap[i]heap[j];//交换元素min_insert(heap,j,item);//把数据item插入到最小堆中}elsemax_insert(heap,i,item);//否则插入到最大堆中break;case false:jmodified_max_partner(i,n);//插入节点在最大堆中对应的节点if(itemheap[j])//比较最大堆节点和插入元素的大小{heap[i]heap[j];//交换元素max_insert(heap,j,item);//插入到最大堆中}elsemin_insert(heap,i,item);//否则插入到最小堆break;}}}int modified_max_partner(int i,int n){double k log(i)/log(2);double a pow(2, (int)k-1);int j;j(i (int)a);if(jn)return j/2;else return NULL;}程序测试#includeHeap.hint main(){int i,item;int n1;for(i2;i{scanf(%d,item);deap_insert(heap,n,item);}for(i2;in;i)printf(%d ,heap[i]);printf(\n);itemdelete_deap_min(heap,n);printf(The deleted data is:%d,item);printf(\n);for(i2;in;i)printf(%d ,heap[i]);return 0;}
