尉氏专业网站建设丹阳网站建设服务

当前位置： 首页 > news >正文

尉氏专业网站建设,丹阳网站建设服务,开平市网站建设,织梦网站模板 虎嗅网TIPS AdjustUp AdjustDown向上调整AdjustUp与向下调整AdjustDown的参数是一个数组#xff08;完全二叉树#xff09;需要进行调整操作的数值的下标/一个数组#xff08;完全二叉树#xff09;堆元素个数需要调整操作的数值的下标。实际上就是对完全二叉树当中的某一点…TIPS AdjustUp AdjustDown向上调整AdjustUp与向下调整AdjustDown的参数是一个数组完全二叉树需要进行调整操作的数值的下标/一个数组完全二叉树堆元素个数需要调整操作的数值的下标。实际上就是对完全二叉树当中的某一点进行调整直至在其局部范围内满足堆的性质。因此对于完全二叉树如果仅仅对若干个值进行AdjustUp/AdjustDown并不会是这颗完全二叉树真正变成一个堆。对于AdjustUp与AdjustDown在没有任何限制与约束的情况之下如果说你对数组完全二叉树中的某一个元素去进行调整的话你可以这么做只不过没有任何意义因为他最终调整调整直至在某一个局部范围内满足堆的性质。既然没有任何意义那它的意义到底是什么呢AdjustUp与AdjustDown的意义就在于建堆。那如果说想使用这两个函数往建堆这条正确的方向去走需要注意AdjustUp的前提必须是在child前面数据已经是一个堆AdjustDown的前提必须是在parent左右两个子树必须是两个堆在这些前提之下如果说你去AdjustUp与AdjustDown那么是真正在朝着建堆前进。不然你在怎么弄的话只是在局部范围内进行兴风作浪对于整体并不能使它变成一个堆。HeapPush HeapPopHeapPush与HeapPop的本质与灵魂就是AdjustUp/AdjustDown。这两个的参数分别是一个堆结构体指针一个需要往堆里面插入的值一个堆结构体指针。因此这两个函数的话需要在原先的数组完全二叉树就是一个堆的情况下才有意义不然的话如果说原先的数组并不是一个堆那么插入一个数的操作与删除第一个元素意义不大。数组完全二叉树建堆向下建堆法O(N)我们讲过一个建堆方式就是说是向上调整法建堆实际上就是不断的插入如果对于一个数据仅仅进行AdjustUp只会最终使得局部范围内满足堆的性质如果说我对数组完全二叉树当中的每一个数都进行AdjustUp那么当我这个操作完了之后这个数组完全二叉树我已经是一个堆了。那有没有其他的方式去建堆呢然后我们再进行向下调整法建堆的时候显而易见的事实就是我说你对叶子就是说没有儿子的节点进行向下调整那还有什么意义没有儿子他调整的也跟白调一样。所以说向下调整法的话我需要从倒着往前走这是第一点这就为了使得AdjustDown朝着建堆的方向走并且从倒着往前走之外我还要从第一个非叶子节点开始进行向下调整。那我该怎么样去找到倒数第一个非叶子节点我只要把最后一个元素的下标child这样(child-1)/2找到他父亲不就万事大吉了吗为什么要倒着走呢因为倒着走去向下调整的时候我就可以确保目前这个节点的左右两个子树都已经是堆这样子的话我就确保AdjustDown的能够朝着正确的方向建堆前进而不是一直在局部范围内在兴风作浪。然后向下调整法建堆的话它的效率比向上调整法建堆要高且差距极大。一般建堆的话是不会用向上调整建堆。当然要对数组完全二叉树建堆首先必须得有两个万金油AdjustUp 与 AdjustDownvoid Swap(int* p1, int* p2) {int tmp *p1;*p1 *p2;p2 tmp; } void AdjustUp(int a, int child) {assert(a);int parent (child - 1) / 2;while (child 0){if (a[parent] a[child]){Swap(a parent, a child);child parent;parent (child - 1) / 2;}else{break;}} } void AdjustDown(int* a, int parent, int n) {assert(a);int child 2 * parent 1;while (childn){if (child1 n a[child] a[child 1]){child;}if (a[parent] a[child]){Swap(a parent, a child);parent child;child 2 * parent 1;}else{break;}} }演示一下向下调整法建堆int main() {int arr[15] { 1,4,5,2,7,8,3,4,9,0,4,3,11,6,8 };int size 15;for (int i (size - 1 - 1) / 2; i 0; i–){AdjustDown(arr, i, size);}return 0; }建堆的核心就在于把AdjustUp与AdjustDown的核心与意义彻底弄清楚以后建堆就关注这两个 数组完全二叉树得有AdjustDown核心奥义堆排序 O(NlogN)堆在我们这边的优点就是说他已经不像之前那样单独的存储数据他能够做到帮我们去选数因此的话从更加程度而言它能够帮助我们排序如果排序的数据量小的话倒还无所谓我说排序的数据量一大那么对于性能的要求就非常重要。与我们之前学过的冒泡排序它的时间复杂度是O(N^2)对堆排序而言的话它的时间复杂度是O(NlogN)。这两个差异极大在堆排序之前的话需要脑子拎清楚的是我们现在已经不是在堆着那个结构体里面了现在我们跟手撕数据结构的那个堆就是说自己手搓的那个堆无关了现在的话相当于就是对题目中给我的数组完全二叉树直接进行建堆然后去进行排序。首先建堆 [ O(N) 向下调整法 ] 数组得有AdjustDown核心奥义要对数组完全二叉树建堆如果你要升序排列就要去建大根堆如果你要降序排列要去建小根堆无论是大根还是小根然后这个数组的顺序确定是从后往前依次慢慢确定下来的。建堆的向下调整法前面已经讲了其次调堆 [堆顶与数组末尾开始去倒] AdjustDown核心奥义当把堆建完之后接下来就是要去换数据了这个过程当中的核心核心成员与利器就是AdjustDown然后每次使用这个函数的时候都需要注意当前这个堆的数据数量是多少是每次都要减1减1的哟。 堆排序时间复杂度堆排序的话除了一开始要把原始数据是数组或者说是完全二叉树建堆之后还要去转数据调堆。对于第一步复杂度是O(N)。然后调堆的时间复杂度也是logN*N用错位相减法减减算算也很快的或者说你用直观的方法去看一下对于最后一层而言如果说你想要确定最后一层堆排序的话它是确定的顺序是从数组的从后往前慢慢确定下来的要确定最后一层的话就需要不断的把堆顶的数据给往下调整这就相当于就是说节点最多的层数它需要调整的次数也是最多。因此对于堆排序而言的话就是说你在一开始对数组完全二叉树建堆的时候无论是用什么方法去建堆最后总的堆排序时间复杂度都是O(N*logN)代码int main() {int arr[10] { 1,4,3,5,7,9,8,6,2,0 };int size 10;//建堆for (int i (size - 1 - 1) / 2; i 0; i–){AdjustDown(arr, i, size);}//调堆int end size - 1;while (end 0){Swap(arr 0, arr end);AdjustDown(arr, 0, end);end–;}return 0; }你会发现在堆排序里面无论是建堆还是调堆都与AdjustUp无关