电子商务网站建设与维护课程总结上海网站设计公司联系方式

电子商务网站建设与维护课程总结,上海网站设计公司联系方式,wordpress手机端不显示内置图片,欧美 电台 网站模板4系列文章目录 文章目录 系列文章目录前言一、堆的定义二、堆的实现1.大/小堆的构建2.堆的增删查 前言 一、堆的定义 结构基础#xff1a;堆是基于完全二叉树的逻辑结构#xff0c;用数组来物理实现。 核心性质#xff1a;堆可分为大堆和小堆。 其中#xff0c;大堆要求每…系列文章目录文章目录系列文章目录前言一、堆的定义二、堆的实现1.大/小堆的构建2.堆的增删查前言一、堆的定义结构基础堆是基于完全二叉树的逻辑结构用数组来物理实现。核心性质堆可分为大堆和小堆。其中大堆要求每个子树的父节点左右子节点。小堆要求每个子树的父节点 左右子节点。//堆用C实现typedefintHPDataType;typedefstructHeap{HPDataType*_a;//堆元素的存放数组int_size;//有效元素个数int_capacity;//容量}Heap;二、堆的实现为什么堆可以用数组来实现因为数组可以实现快速的随机访问操作更加简单。再加上完全二叉树不会浪费很多数组的空间。1.大/小堆的构建以小堆为例为了让最小的数在堆顶其余的小数都在其子树的父亲节点。要用到“向下调整”的算法。来调整根节点和两子树的关系是根保持为最小。当parent n, 左 child 2 * n 1, 右child 2 * n 2 基于数组实现的索引规律//参数分别为 堆中元素(数组)元素总个数需要向下调整的父亲节点voidAdjustdowm(HPDataType*a,intn,introot){intparentroot;intchild2*parent1;//先假设左孩子while(childn)//结束条件孩子节点不能大于总数{if(childna[child]a[child1]){child;//右孩子小,使child走到右孩子}//如果孩子节点小于父亲节点if(a[child]a[parent]){swap(a[child],a[parent]);parentchild;childparent*21;}else{break;}}}但向下调整的前提是单前节点的左右子树都是小堆才能保证拿上来的是最小值。所以要从最后一个节点的父亲节点开始向下调整由下到上。当孩子child n时parent (n-1) /2 最后一个孩子是n-1, 得出最后一个父亲是(n-1-1)/2//构建堆——以小堆为例for(inti(n-1-1)/2;i0;i--)//从最后一个节点的父亲节点开始从下往上才能保证左右子树都是小堆{AdjustDown(hp-_a,hp-_size,i);}2.堆的增删查如何在堆中增加一个数而不破坏小堆的形式先把数据加在末尾再使用向上调整算法使数据到合适的地方。//向上调整---以小堆为例AdjustUp(HPDataType*a,intn,intchild){intparent(child-1)/2;while(child0)//当child 0时才算调整完{if(a[child]a[parent]){swap(a[child],a[parent]);childparent;parent(child-1)/2;}else{break;}}}增加一个元素// 堆的插入voidHeapPush(Heap*hp,HPDataType x){//插入时只能先在末尾插入再调整到堆中合适的地方if(hp-_sizehp-_capacity){hp-_capacity*2;HPDataType*tmp(HPDataType*)realloc(hp-_a,sizeof(HPDataType)*hp-_capacity);if(tmp!NULL){hp-_atmp;}else{printf(扩容失败);}}hp-_a[hp-_size]x;//需要将插入值向上调整AdjustUp(hp-_a,hp-_size,hp-_size-1);}删堆顶的数据是先将堆顶与数组最后一个元素交换再删除最后一个元素将新元素向下调整。因为最后一个元素方面删除。// 堆的删除——肯定删的是堆顶的数据voidHeapPop(Heap*hp){intendhp-_size-1;if(end0){return;}else{swap(hp-_a[0],hp-_a[end]);hp-_size--;AdjustDown(hp-_a,hp-_size,0);}}