flash网站作品欣赏个人求职网站设计

flash网站作品欣赏,个人求职网站设计,邯郸市建设局网站政策,wordpress 建站完全二叉树完全二叉树是一种特殊的二叉树结构#xff0c;所有层#xff08;除最后一层外#xff09;的节点都完全填满#xff0c;且最后一层的最后一层节点尽可能从左到右连续排列。例如#xff1a;1/ \2 3/ \ /4 5 6堆只分为小顶堆和大顶堆。小顶堆和大顶堆小顶…完全二叉树完全二叉树是一种特殊的二叉树结构所有层除最后一层外的节点都完全填满且最后一层的最后一层节点尽可能从左到右连续排列。例如1 / \ 2 3 / \ / 4 5 6堆只分为小顶堆和大顶堆。小顶堆和大顶堆小顶堆是一种完全二叉树每个父节点的值小于或等于其子节点的值。1 / \ 3 2 / \ / 4 6 5 [1,3,2,4,6,5]大顶堆也是一种完全二叉树每个父节点的值大于或等于其子节点的值。9 / \ 7 5 / \ / 4 6 3 [9,7,5,4,6,3]向上调整和向下调整单次调整典型的例子就是堆的尾增和首删。尾删很容易直接删最后一个数据堆的尾增向上调整堆的尾增操作通常指在堆的末尾插入新元素后通过向上调整Heapify Up维护堆的性质。第一步插入元素到末尾将新元素插入堆的最后一个位置数组末尾保持完全二叉树的结构。第二步向上比较交换从插入位置开始比较当前节点与其父节点的值。大顶堆时若当前节点值大于父节点值小顶堆则是小于则交换两者位置并继续向上比较直到满足堆的性质或到达根节点。时间复杂度最坏情况下需从叶子节点调整到根节点复杂度为O(log N)。逐步演示现在有小顶堆1 / \ 3 5 / \ / 4 8 6 [1, 3, 5, 4, 8, 6]插入新元素在堆末尾插入元素21 / \ 3 5 / \ / \ 4 8 6 2 [1, 3, 5, 4, 8, 6, 2]向上调整比较新节点与父节点由于2 5不满足最小堆性质交换两者。1 / \ 3 2 / \ / \ 4 8 6 5 [1, 3, 2, 4, 8, 6, 5]继续判断比较其与新的父节点由于2 1满足最小堆性质停止交换。算法终止。堆的首删向下调整堆的首删操作通常指删除堆顶元素后通过向下调整Heapify Down维护堆的性质。第一步交换并删除堆顶元素将堆顶元素根节点与堆的最后一个元素交换位置随后删除末尾元素原堆顶。保持完全二叉树的结构。第二步向下比较交换从新的堆顶开始比较当前节点与其左右子节点的值。大顶堆时若当前节点值小于较大子节点值小顶堆则是大于则交换两者位置并继续向下比较直到满足堆的性质或到达叶子节点。时间复杂度最坏情况下需从根节点调整到叶子节点复杂度为O(log N)。逐步演示小顶堆初始堆1 / \ 3 5 / \ / 4 8 6 [1, 3, 5, 4, 8, 6]删除堆顶元素1.交换堆顶1与末尾元素66 / \ 3 5 / \ 4 8 [6, 3, 5, 4, 8]2.向下调整比较新堆顶6与左右子节点3和5选择较小子节点3。由于6 3交换两者3 / \ 6 5 / \ 4 8 [3, 6, 5, 4, 8]继续调整节点6比较其与子节点4和8选择较小子节点4。由于6 4交换两者3 / \ 4 5 / \ 6 8 [3, 4, 5, 6, 8]节点6无子节点调整终止,算法结束。向上调整建堆是一种将无序数组转换为堆结构的方法。其核心思想是从第二个节点开始逐步向后调整每个子树即反复使用上文的单次的向上调整使其满足堆的性质最大堆或最小堆。目标大顶堆 5 / \ 3 6 / \ / \ 7 5 1 9 从3开始调整然后是6 7 5 1 9。 3不用调整6要调整 6 / \ 3 5 / \ / \ 7 5 1 9 7要调整 9 / \ 6 7 / \ / \ 3 5 1 5 9要调整已经是最后一位算法结束。时间复杂度分析第1层2^0个结点需要向上移动0层第2层 2^1 个结点需要向上移动1层第3层 2^2 个结点需要向上移动2层第4层 2^3 个结点需要向上移动3层......第h层 2^h−1个结点需要向上移动h-1层则需要移动结点总的移动步数为每层结点个数 * 向上调整次数第⼀层调整次数为0T(h) 2^1 ∗ 1 2^2 ∗ 2 2^3 ∗ 3 .. 2^h−2∗ (h− 2) 2^h−1∗ (h− 1)①数学计算得T(h) −(2^​​​​​​​h− 1) 2^​​​​​​​h∗ (h− 1) 2^0根据⼆叉树的性质n 2h− 1和hlog2(n 1)T(n) −N 2^​​​​​​​h∗ (h− 1) 2^0F(h) 2^h(h− 2) 2F(n) (n 1)(log(n 1) − 2) 2由此可得向上调整算法建堆时间复杂度为O(nlogn)向下调整建堆是一种将无序数组转换为堆结构的方法。其核心思想是从最后一个非叶子节点开始逐步向前调整每个子树即反复使用上文的单次的向下调整使其满足堆的性质最大堆或最小堆。目标大顶堆 5 / \ 3 6 / \ / \ 7 5 1 9 从6开始调整然后是35。 6要调整6和子节点19都比较最终选择和9交换 5 / \ 3 9 / \ / \ 7 5 1 6 3要调整 5 / \ 7 9 / \ / \ 3 5 1 6 5要向下调整两次 9 / \ 7 6 / \ / \ 3 5 1 5 已经是第一位算法结束。时间复杂度第1层2^0个结点需要向下移动h-1层第2层 2^1 个结点需要向下移动h-2层第3层 2^2 个结点需要向下移动h-3层第4层 2^3 个结点需要向下移动h-4层......第h-1层 2^h−2个结点需要向下移动1层则需要移动结点总的移动步数为每层结点个数 * 向下调整次数T(h) 20∗ (h− 1) 21∗ (h− 2) 22∗ (h− 3) 23∗ (h− 4) .. 2h−3∗ 2 2h−2∗ 1由数学计算T(h) 2^h− 1 −h根据⼆叉树的性质n 2^h− 1和hlog2(n 1)T(n) n−log2(n 1) ≈n向下调整算法建堆时间复杂度为O(n)为什么向下调整算法比向上调整算法块因为向下调整算法下面的层节点多移动次数少。而向上调整算法下面的层节点多移动次数也多。如果有已给定的数组一般使用向下调整建堆。Top-K问题最优解是用堆排序。比如找到全国最富有的十个人。第一步用任意10人建小顶堆 → 次数可忽略≈常数第二步遍历剩余 14亿-10 人逐个判断调整和堆顶比如果比顶堆大那就是比第十名富有第十名要淘汰而他要插进去替换堆顶向下调整​第三步全部比完后留在堆中就是最富有的十个人。时间复杂度O(nlogK)