二叉树-堆1

完美二叉树若像下图这样写当child为堆顶时计算parent为0不会是-0.5向上取整为0while判断parent为0符合条件进入循环此时ifa[child]a[parent],跳出循环。这只是程序能巧合运行将代码循环条件改为child0,即优化为上面代码即可向下调整算法1.接口是 HPDataType* a, int n, int parent2.算出孩子child以左孩子为例使用假设法始终让child为小的孩子3.1将parent与孩子对比若孩子小于双亲则交换同时继续判断交换下去的值是否需要再次交换所以将parent改为child重新计算child。2 否则break4.while循环若直至child到从下往上第一层parent为从下往上第二层若再执行一次31child不存在(超出了数组)此时child与parent都是从下往上第一层同一个节点不需要再循环所以循坏结束条件是childn.pop 删除在小堆的基础上用插入包含向上调整法根的左右子树是小堆交换首尾元素后删除尾元素左子树和右子树是小堆,将最小的堆顶元素交换到数组尾部然后使用向下调整算法将首元素与下面的两个元素中小的元素依次交换交换到不能交换为止建立小堆。删除的都是剩余数据中最小的数据所以会由小到大依次删除数据孩子给双亲以 以下图中算法给数组进行堆排序HPPush函数传的是结构体变量地址该函数额外申请内存存放堆需要消耗额外的空间来存放堆空间复杂度O(n)Destroy(hp);}以下图片没有传结构体变量指针原因而是直接传数组首元素地址直接在所给数组基础上排序不用再调用排序函数排序函数需要消耗额外的空间减少空间复杂度以下算法直接在所给数组上进行堆排序不用再调用排序函数减少空间复杂度向上调整算法排序数组/向下调整算法排序数组向上调整算法/向下调整算法可以分别构建大和小堆将无序的数组用向上调整算法/向下调整算法重新排列成小堆以向上调整算法建小堆为例再将数组的首尾元素交换此时尾元素不在数组中算将数组用向下调整法重新拍列成小堆将数组长度减一重复循环至循环结束即可得到一个由大到小的数组。即下方的//降序建小堆。反之亦然。void HeapSort(int* a, int n){// 降序建小堆// 升序建大堆for (int i 1; i n; i) 因为是直接在数组本身上调整排序所以直接从第二个元素开始与第 一个元素比较{AdjustUp(a, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}}void TestHeap2(){int a[] { 4,2,8,1,5,6,9,7,2,7,9};HeapSort(a, sizeof(a) / sizeof(int));}int main(){TestHeap2();return 0;}向下调整算法排序数组还有另外一种算法按照大堆重新排列为了确保除根外的左右子树是按大堆排列我们可以从倒数第一个非叶子节点最后一个元素的双亲节点开始用向下调整算法调大堆倒数第二个非叶子节点开始调大堆以此类推直至除根外的左右子树是按大堆排列然后再用向下调整算法将无序的数组用向下调整算法建堆按照大堆重新排列再将数组的首尾元素交换此时尾元素不在数组中算将数组用向下调整法重新拍列成大堆将数组长度减一重复循环至循环结束。即可得到一个由小到大的数组。即下方的//降序建小堆。void HeapSort(int* a, int n){for (int i (n-1-1)/2; i 0; i--){AdjustDown(a, n, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}}void TestHeap2(){int a[] { 4,2,8,1,5,6,9,7,2,7,9};HeapSort(a, sizeof(a) / sizeof(int));}int main(){TestHeap2();return 0;}向上调整算法logN向下调整算法logN向上调整算法排序数组O(N*logN)向下调整算法排序数组O(N*logN)向下调整算法建堆O(N)循环条件