当前位置： 面试刷题>> 堆化操作 (经典算法题500道)
### 题目描述补充
**题目：堆化操作**
给定一个数组（列表），要求将其转换为一个最大堆（或最小堆，根据题目要求而定）。堆是一种特殊的完全二叉树结构，其中每个父节点的值都大于或等于（对于最大堆）或小于或等于（对于最小堆）其所有子节点的值。数组中的元素按照层序遍历的顺序存储，即对于索引为i的元素，其左子节点的索引为2*i+1，右子节点的索引为2*i+2，父节点的索引为(i-1)/2（向下取整）。
**要求**：
1. 编写一个函数，该函数接受一个数组作为输入，并将其转换为最大堆（或最小堆）。
2. 给出PHP、Python、JavaScript的示例代码实现。
### 示例代码
#### PHP 示例
```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 示例
```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 示例
```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);
```
码小课网站中有更多关于堆、数据结构与算法的相关内容分享给大家学习，欢迎访问码小课网站深入学习！