如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。
给定一个整数数组arr[] ，从给定的数组构建一个最大堆。
最大堆是一种完全二叉树，其中每个父节点都大于或等于其子节点，从而确保最大元素位于根节点。
例如：
输入： arr[] = [4, 10, 3, 5, 1]
输出：对应的最大堆：
输入：arr[] = [1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17]
输出：对应的最大堆：
【方法】使用递归——时间复杂度为 O(n)，空间复杂度为 O(log n)
要从数组构建最大堆，可以将数组视为完全二叉树，并按逆序从最后一个非叶子节点开始堆化到根节点。叶子节点已经满足堆的性质，因此我们从最后一个非叶子节点开始，对于每个子树，我们比较其父节点和子节点。每当子节点大于父节点时，我们就交换它们，并继续堆化该子树，以确保最大堆的性质始终保持不变。
笔记 ：
根节点位于索引 0 处。
节点 i 的左子节点 -> 2*i + 1。
节点 i 的右子节点 -> 2*i + 2。
节点 i 的父节点 -> (i-1)/2。
最后一个非叶子节点 -> 最后一个节点的父节点 -> (n/2) – 1。
示例代码：
// To heapify a subtree rooted
function heapify(arr, n, i) {
let largest = i;
let l = 2 * i + 1;
let r = 2 * i + 2;
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// Function to build a Max-Heap from the given array
function buildHeap(arr) {
const n = arr.length;
// Index of last non-leaf node
let startIdx = Math.floor(n / 2) – 1;
// Perform reverse level order traversal
// from last non-leaf node and heapify
// each node
for (let i = startIdx; i >= 0; i–) {
heapify(arr, n, i);
}
}
// Driver Code
// Binary Tree Representation of input array
// 1
// / \\
// 3 5
// / \\ / \\
// 4 6 13 10
// / \\ / \\
// 9 8 15 17
const arr = [1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17];
const n = arr.length;
// Build Max Heap
buildHeap(arr);
for (let i = 0; i < n; i++)
process.stdout.write(arr[i] + " ");
console.log("\\n");
// Final Heap Representation
// 17
// / \\
// 15 13
// / \\ / \\
// 9 6 5 10
// / \\ / \\
// 4 8 3 1
输出
17 15 13 9 6 5 10 4 8 3 1
如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。
