关于营销的网站有哪些内容,怎么浏览国外的设计网站,杭州网站建设 乐云践新专家,网络营销运营推广1.容器 容器用于容纳元素集合#xff0c;并对元素集合进行管理和维护#xff0e; 传统意义上的管理和维护就是#xff1a;增#xff0c;删#xff0c;改#xff0c;查#xff0e; 我们分析每种类型容器时#xff0c;主要分析其增#xff0c;删#xff0c;改#xff…1.容器 容器用于容纳元素集合并对元素集合进行管理和维护 传统意义上的管理和维护就是增删改查 我们分析每种类型容器时主要分析其增删改查动作实现及复杂度
2.堆 2.1.结构 2.1.1.图解 堆是容器类型 采用容器内元素在线性空间连续存储的组织方式数组也是如此 但除此之外基于元素的组织方式为其抽象出了一层二叉树的逻辑关系
以一个具体实例来说明 上图是代表了一个可容纳12个元素的线性空间现在存储了8个有效元素堆的元素存储和数组一致 但堆为其顺序存储的元素抽象出了一层二叉树的逻辑关系 抽象的过程为对顺序存储的每个元素依次用这些元素顺序填满一颗满二叉树 所谓满二叉树指的是除了树最后一层其余各层均是满的最后一层最后一个元素左边各个元素均是存在的
如果观察特点可以得出以下结论对顺序存储中索引为nIndex的元素 逻辑结构里其左孩子是索引为(2*nIndex1)的元素其右孩子是索引为(2*nIndex2)的元素
堆针对逻辑结构又施加了一层限制 对最大堆来说这层限制是对堆中任一元素该元素需要大于等于其左孩子其右孩子上的元素 对最小堆来说这层限制是对堆中任一元素该元素需小于等于其左孩子其右孩子上的元素
在以上条件均满足下可被利用的性质是 (1). 首个元素是所有元素中最大的对最大堆最小的对最小堆 (2). 抽象出来的二叉树由于是满二叉树其高度为log以2为底n的对数
2.1.2.存在一致性约束容器特点 (1). 插入无需提供位置信息 (2). 不支持直接原地修改一般分解为移除添加两个过程 (3). 由于元素值决定其位置这类容器一般插入元素时以std::pairkey, value形式插入即元素包含键值两部分键用来实现一致性约束值是此键关联的实际内容
2.2.动作 2.2.0.建堆 意思是直接给一个连续存储的元素集合把这些元素集合调整为符合堆性质的元素集合 最直观当然是对集合内每个元素直接执行插入这样所有元素插入完毕就得到一个由这些元素构成的堆 这里介绍另一种方式 从集合最后一个元素反向遍历到第一个元素 对每次遍历到的元素让其符合以该元素为根子树中所有元素均满足堆的性质
下面介绍针对每个遍历到元素的调节过程 不妨假设我们现在遍历到的元素是p假设是最小堆 由于我们之前每次遍历时均按上述要求所以p的左孩子为根子树中所有元素此时均满足堆的性质p的右孩子为根子树也是如此此刻子树中唯一可能不满足要求的就是p和其左右孩子 若p小于其左右孩子上的元素则无需调节 否则找到三者中最小元素q交换此q和p的位置 交换后对p和其左右孩子来说堆的性质得到满足但对q来说由于此位置元素变大了所以此刻子树中只有q与其左右孩子可能不满足堆的性质这样我们虽然未立即解决问题但将问题转化为了一个同类型问题 由于树的高度有限每次转化后我们在更低一层子树上再次处理同类问题 故即使最坏下至多经过有限次调节也可解决问题
2.2.1.增 堆中插入新元素对于存在一致性约束的容器元素插入到容器后需经历调节过程不需要也无法在指定位置实现插入具体位置依赖调节过程
插入过程可描述为 (1). 将新元素放在数组尾后位置 (2). 这样此时数组对应的二叉树中只有新节点p和其父亲q可能不满足堆的性质 (3). 我们分析最小堆场景比较p和q若q中元素小于等于p则无需调节 (4). 若q中元素大于p交换pq内元素交换后由于q位置元素变小了所以q和其父节点可能不满足堆的性质p位置元素变小了故以p和其左右孩子必然满足堆的性质
这样我们虽然未立即解决问题但将问题转化了由于树的高度有限故最坏下也能经过有限次迭代结束调节过程
2.2.2.删 堆由于其性质一般移除限定只能移除首个元素我们分析移除首个元素过程
删除首元素可描述为 (1). 交换尾元素和首元素递减有效元素数量 (2). 我们分析最小堆场景此时首元素p相比原来变大了此时整棵树中只有p和其左右孩子可能不满足堆的性质 (3). 我们寻找节点p其左孩子lp其右孩子rp三者中最小元素及其位置 (4). 若最小元素是p则无需调节 (5). 若最小元素是某个孩子cp(要么lp要么rp)交换cp和p上元素这样交换后p和其左右孩子此时满足了堆的性质但cp上元素变大了所以此时cp和其左右孩子可能不满足堆的性质
这样我们虽然未能立即解决问题但将问题转化了由于树的高度有限故最环下也能经过有限次迭代结束调节过程
2.2.3.查 堆一般只提供访问首元素方法即可 访问首元素直接基于索引访问即可
2.2.4.改 对于存在一致性约束的容器一般不会允许直接修改元素的值 此类操作一般分解为删除老元素添加新元素两个过程来实现
删除非首元素类似删除首元素过程只不过此时先交换删除位置元素和尾部元素再从此开始进入调节流程
2.3.时间复杂度 评价容器的依据一个是其占据的线性空间一个是操作执行的时间复杂度 堆的各个操作时间复杂度为 (1). 增Θ(log以2为底n的对数) (2). 删Θ(log以2为底n的对数) (3). 查Θ(1) (索引访问) (4). 改Θ(1) (log以2为底n的对数)
