题目描述补充

题目：堆化操作

给定一个数组（列表），要求将其转换为一个最大堆（或最小堆，根据题目要求而定）。堆是一种特殊的完全二叉树结构，其中每个父节点的值都大于或等于（对于最大堆）或小于或等于（对于最小堆）其所有子节点的值。数组中的元素按照层序遍历的顺序存储，即对于索引为i的元素，其左子节点的索引为2i+1，右子节点的索引为2i+2，父节点的索引为(i-1)/2（向下取整）。

要求：

1. 编写一个函数，该函数接受一个数组作为输入，并将其转换为最大堆（或最小堆）。
2. 给出PHP、Python、JavaScript的示例代码实现。

示例代码

PHP 示例

function heapify(&$arr, $n, $i) {
    $largest = $i;
    $left = 2 * $i + 1;
    $right = 2 * $i + 2;

    if ($left < $n && $arr[$left] > $arr[$largest]) {
        $largest = $left;
    }

    if ($right < $n && $arr[$right] > $arr[$largest]) {
        $largest = $right;
    }

    if ($largest != $i) {
        swap($arr, $i, $largest);
        heapify($arr, $n, $largest);
    }
}

function swap(&$arr, $i, $j) {
    $temp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $temp;
}

function buildMaxHeap(&$arr) {
    $n = count($arr);
    for ($i = floor(($n - 1) / 2); $i >= 0; $i--) {
        heapify($arr, $n, $i);
    }
}

// 示例
$arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
buildMaxHeap($arr);
print_r($arr);

Python 示例

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def buildMaxHeap(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

# 示例
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
buildMaxHeap(arr)
print(arr)

JavaScript 示例

function heapify(arr, n, i) {
    let largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, n, largest);
    }
}

function buildMaxHeap(arr) {
    let n = arr.length;
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

// 示例
let arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
buildMaxHeap(arr);
console.log(arr);

码小课网站中有更多关于堆、数据结构与算法的相关内容分享给大家学习，欢迎访问码小课网站深入学习！