Heapify方法的设计与分析

Heapify 方法重新排列数组的元素，其中第i个元素的左右子树遵循堆属性。

Algorithm: Max-Heapify(numbers[], i) 
leftchild := numbers[2i] 
rightchild := numbers [2i + 1] 
if leftchild ≤ numbers[].size and numbers[leftchild] > numbers[i] 
   largest := leftchild 
else 
   largest := i 
if rightchild ≤ numbers[].size and numbers[rightchild] > numbers[largest] 
   largest := rightchild 
if largest ≠ i 
   swap numbers[i] with numbers[largest] 
   Max-Heapify(numbers, largest)

当提供的数组不遵守堆属性时，将基于以下算法构建堆：Build-Max-Heap (numbers[])。

Algorithm: Build-Max-Heap(numbers[]) 
numbers[].size := numbers[].length 
fori = ⌊ numbers[].length/2 ⌋ to 1 by -1 
   Max-Heapify (numbers[], i)

例子

C C++ Java Python 
#include <stdio.h>
void swap(int arr[], int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
void maxHeapify(int arr[], int size, int i) {
    int leftChild = 2 * i + 1;
    int rightChild = 2 * i + 2;
    int largest = i;
    if (leftChild < size && arr[leftChild] > arr[largest])
        largest = leftChild;
    if (rightChild < size && arr[rightChild] > arr[largest])
        largest = rightChild;
    if (largest != i) {
        swap(arr, i, largest);
        maxHeapify(arr, size, largest); // Recursive call to continue heapifying
    }
}
void buildMaxHeap(int arr[], int size) {
    for (int i = size / 2 - 1; i >= 0; i--)
        maxHeapify(arr, size, i); // Start heapifying from the parent nodes in bottom-up order
}
int main() {
    int arr[] = { 3, 10, 4, 5, 1 }; // Initial Max-Heap (or any array)
    int size = sizeof(arr) / sizeof(arr[0]);
    buildMaxHeap(arr, size); // Build the Max-Heap from the given array
    printf("Max Heap: ");
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]); // Print the updated Max-Heap
    printf("\n");
    return 0;
}

输出

Max Heap: 10 5 4 3 1 

#include <iostream>
#include <vector>
void swap(std::vector<int>& arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
void maxHeapify(std::vector<int>& arr, int size, int i) {
    int leftChild = 2 * i + 1;
    int rightChild = 2 * i + 2;
    int largest = i;
    if (leftChild < size && arr[leftChild] > arr[largest])
        largest = leftChild;
    if (rightChild < size && arr[rightChild] > arr[largest])
        largest = rightChild;
    if (largest != i) {
        swap(arr, i, largest);
        maxHeapify(arr, size, largest); // Recursive call to continue heapifying
    }
}
void buildMaxHeap(std::vector<int>& arr, int size) {
    for (int i = size / 2 - 1; i >= 0; i--)
        maxHeapify(arr, size, i); // Start heapifying from the parent nodes in bottom-up order
}
int main() {
    std::vector<int> arr = { 3, 10, 4, 5, 1 }; // Initial Max-Heap (or any array)
    int size = arr.size();
    buildMaxHeap(arr, size); // Build the Max-Heap from the given array
    std::cout << "Max Heap: ";
    for (int i = 0; i < size; i++)
        std::cout << arr[i] << " "; // Print the updated Max-Heap
    std::cout << std::endl;
    return 0;
}

输出

Max Heap: 10 5 4 3 1

import java.util.Arrays;
public class MaxHeap {
    public static void swap(int arr[], int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void maxHeapify(int arr[], int size, int i) {
        int leftChild = 2 * i + 1;
        int rightChild = 2 * i + 2;
        int largest = i;
        if (leftChild < size && arr[leftChild] > arr[largest])
            largest = leftChild;
        if (rightChild < size && arr[rightChild] > arr[largest])
            largest = rightChild;
        if (largest != i) {
            swap(arr, i, largest);
            maxHeapify(arr, size, largest); // Recursive call to continue heapifying
        }
    }
    public static void buildMaxHeap(int arr[]) {
        int size = arr.length;
        for (int i = size / 2 - 1; i >= 0; i--)
            maxHeapify(arr, size, i); // Start heapifying from the parent nodes in bottom-up order
    }
    public static void main(String args[]) {
        int arr[] = { 3, 10, 4, 5, 1 }; // Initial Max-Heap (or any array)
        buildMaxHeap(arr); // Build the Max-Heap from the given array
        System.out.print("Max Heap: ");
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " "); // Print the updated Max-Heap
        System.out.println();
    }
}

输出

Max Heap: 10 5 4 3 1 

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]
def max_heapify(arr, size, i):
    left_child = 2 * i + 1
    right_child = 2 * i + 2
    largest = i
    if left_child < size and arr[left_child] > arr[largest]:
        largest = left_child
    if right_child < size and arr[right_child] > arr[largest]:
        largest = right_child
    if largest != i:
        swap(arr, i, largest)
        max_heapify(arr, size, largest) # Recursive call to continue heapifying    
def build_max_heap(arr):
    size = len(arr)
    for i in range(size // 2 - 1, -1, -1):
        max_heapify(arr, size, i) # Start heapifying from the parent nodes in bottom-up order
arr = [3, 10, 4, 5, 1] # Initial Max-Heap (or any array)
build_max_heap(arr) # Build the Max-Heap from the given array
print("Max Heap:", arr) # Print the updated Max-Heap

输出

Max Heap: [10, 5, 4, 3, 1]