餐饮vi设计网站,网站定位要点 有哪些方面,做网站数据库,专业微信网站建设价格堆和栈的区别#xff1a;一、堆栈空间分配区别#xff1a;1、栈#xff08;操作系统#xff09;#xff1a;由操作系统自动分配释放 #xff0c;存放函数的参数值#xff0c;局部变量的值等。其操作方式类似于数据结构中的栈#xff1b;2、堆#xff08;操作系统… 堆和栈的区别一、堆栈空间分配区别1、栈操作系统由操作系统自动分配释放 存放函数的参数值局部变量的值等。其操作方式类似于数据结构中的栈2、堆操作系统 一般由程序员分配释放 若程序员不释放程序结束时可能由OS回收分配方式倒是类似于链表。二、堆栈缓存方式区别1、栈使用的是一级缓存 他们通常都是被调用时处于存储空间中调用完毕立即释放2、堆是存放在二级缓存中生命周期由虚拟机的垃圾回收算法来决定并不是一旦成为孤儿对象就能被回收。所以调用这些对象的速度要相对来得低一些。三、堆栈数据结构区别堆数据结构堆可以被看成是一棵树如堆排序栈数据结构一种先进后出的数据结构。 http://blog.csdn.net/genios/article/details/8157031 最大堆和最小堆是二叉堆的两种形式。 最大堆根结点的键值是所有堆结点键值中最大者且每个结点的值都比其孩子的值大。 最小堆根结点的键值是所有堆结点键值中最小者且每个结点的值都比其孩子的值小。 最小堆和最大堆的增删改相似其实就是把算法中的大于改为小于把小于改为大于。 生成最大堆最大堆通常都是一棵完全二叉树因此我们使用数组的形式来存储最大堆的值从1号单元开始存储因此父结点跟子结点的关系就是两倍的关系。 即heap[father * 2] heap[leftChild]; heap[father * 2 1] heap[rightChild]; 最大堆的初始化 在生成最大堆时我们可以采取一次次遍历整棵树找到最大的结点放到相应的位置中。 但是这种方法有个不好的地方就是每个结点都要重复比较多次。 所以我们可以换一种思考的顺序从下往上进行比较。先找到最后一个有子结点的结点先让他的两个子结点进行比较找到大的值再和父结点的值进行比较。如果父结点的 值小则子结点和父结点进行交换交换之后再往下比较。然后一步步递归上去知道所在结点的位置是0号位置跳出。这样就可以有效地减少比较所用到的时间。 但是每一次交换都要重复三步heap[i] temp; heap[i] heap[j]; heap[j] temp; 当树的结构比较大的时候就会浪费很多时间。 所以我们可以先把父结点的值存到temp中跟子结点比较如果子结点大的话就把子结点的值赋值给父结点再往下比较最后才把temp的值存到相应的位置。 [cpp] view plaincopy print? void Initialize(T a[], int size, int ArraySize) { delete []heap; isExist false; heap a; CurrentSize size; MaxSize ArraySize; //产生一个最大堆 for(int i CurrentSize / 2; i 1; i --) { T y heap[i]; //子树的根 //寻找放置y的位置 int c 2 * i; //c的父节点是y的目标位置 while(c CurrentSize) { //heap[c应是较大的同胞节点 if(c CurrentSize heap[c] heap[c 1]) c ; //能把y放入heap[c / 2]吗 if(y heap[c]) break; //能 else //不能 { heap[c / 2] heap[c]; //将孩子上移 c * 2; } //下移一层 } heap[c / 2] y; } } 最大堆的插入 最大堆的插入的思想就是先在最后的结点添加一个元素然后沿着树上升。跟最大堆的初始化大致相同。 [cpp] view plaincopy print? MaxHeapT Insert(const Tx) { if(CurrentSize MaxSize) exit(1); //没有足够空间 //为x寻找应插入位置 //i从新的叶节点开始并沿着树上升 int i CurrentSize; while(i ! 1 x heap[i/2]) { //不把x放进heap[i] heap[i] heap[i/2]; //元素下移 i / 2; //移向父节点 } heap[i] x; //这时候才把x放进去 return *this; } 最大堆的删除 最大堆的删除即删除最大的元素。我们先取最后的元素提到根结点然后删除最大值然后再把新的根节点放到合适的位置 [cpp] view plaincopy print? MaxHeapT DeleteMax(T x) { //检查堆是否为空 if(CurrentSize 0) exit(1); //队列空 x heap[1]; //最大元素 T y heap[CurrentSize--]; //最后一个元素 //从根开始重构大堆 int i 1, ci 2; //ci为i的儿子 while(ci CurrentSize) { if(ci CurrentSize heap[ci] heap[ci 1]) //比较两个子节点大小取其大 ci ; //能否放y if(heap[ci] y) //不能 { heap[i] heap[ci]; //孩子上移 i ci; //下移一层 ci * 2; } else //能 break; } heap[i] y; return *this; }
