C语言 从数组构建堆(Building Heap from Array)

目录例如【方法】使用递归——时间复杂度为 O(n)空间复杂度为 O(log n)示例代码如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。给定一个整数数组arr[] 从给定的数组构建一个最大堆。最大堆是一种完全二叉树其中每个父节点都大于或等于其子节点从而确保最大元素位于根节点。例如输入 arr[] [4, 10, 3, 5, 1]输出对应的最大堆输入arr[] [1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17]输出对应的最大堆【方法】使用递归——时间复杂度为 O(n)空间复杂度为 O(log n)要从数组构建最大堆可以将数组视为完全二叉树并按逆序从最后一个非叶子节点开始堆化到根节点。叶子节点已经满足堆的性质因此我们从最后一个非叶子节点开始对于每个子树我们比较其父节点和子节点。每当子节点大于父节点时我们就交换它们并继续堆化该子树以确保最大堆的性质始终保持不变。笔记 1、根节点位于索引 0 处。2、节点 i 的左子节点 - 2*i 1。3、节点 i 的右子节点 - 2*i 2。4、节点 i 的父节点 - (i-1)/2。5、最后一个非叶子节点 - 最后一个节点的父节点 - (n/2) - 1。示例代码#include stdio.h#include stdlib.h// To heapify a subtreevoid heapify(int arr[], int n, int i){// Initialize largest as rootint largest i;int l 2 * i 1;int r 2 * i 2;// If left child is larger than rootif (l n arr[l] arr[largest])largest l;// If right child is larger than largest so farif (r n arr[r] arr[largest])largest r;// If largest is not rootif (largest ! i) {int temp arr[i];arr[i] arr[largest];arr[largest] temp;// Recursively heapify the affected sub-treeheapify(arr, n, largest);}}// Function to build a Max-Heap from the given arrayvoid buildHeap(int arr[], int n){// Index of last non-leaf nodeint startIdx (n / 2) - 1;// Perform reverse level order traversal// from last non-leaf node and heapify// each nodefor (int i startIdx; i 0; i--) {heapify(arr, n, i);}}int main(){// Binary Tree Representation// of input array// 1// / \// 3 5// / \ / \// 4 6 13 10// / \ / \// 9 8 15 17int arr[] {1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17};int n sizeof(arr) / sizeof(arr[0]);// Function callbuildHeap(arr, n);for (int i 0; i n; i)printf(%d , arr[i]);printf(\n);// Final Heap:// 17// / \// 15 13// / \ / \// 9 6 5 10// / \ / \// 4 8 3 1return 0;}输出17 15 13 9 6 5 10 4 8 3 1如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。