java代码如何实现堆结构及堆排序功能 java代码堆数据结构的基础编写教程​

MaxHeap

ArrayList

ArrayList

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

public class MaxHeap {
    private List<Integer> heap;

    public MaxHeap() {
        this.heap = new ArrayList<>();
    }

    // 插入元素
    public void insert(int value) {
        heap.add(value);
        heapifyUp(heap.size() - 1); // 新元素可能破坏堆属性，需要上浮
    }

    // 提取最大元素（堆顶）
    public int extractMax() {
        if (isEmpty()) {
            throw new NoSuchElementException("Heap is empty.");
        }
        int max = heap.get(0);
        int lastElement = heap.remove(heap.size() - 1); // 移除最后一个元素
        if (!isEmpty()) {
            heap.set(0, lastElement); // 将最后一个元素放到堆顶
            heapifyDown(0); // 新堆顶可能破坏堆属性，需要下沉
        }
        return max;
    }

    // 查看最大元素（不移除）
    public int peekMax() {
        if (isEmpty()) {
            throw new NoSuchElementException("Heap is empty.");
        }
        return heap.get(0);
    }

    public boolean isEmpty() {
        return heap.isEmpty();
    }

    public int size() {
        return heap.size();
    }

    // 元素上浮操作：当新元素插入或元素值增大时，将其向上移动以维护堆属性
    private void heapifyUp(int index) {
        int parentIndex = (index - 1) / 2; // 计算父节点索引
        while (index > 0 && heap.get(index) > heap.get(parentIndex)) {
            swap(index, parentIndex);
            index = parentIndex;
            parentIndex = (index - 1) / 2;
        }
    }

    // 元素下沉操作：当堆顶元素被移除或元素值减小时，将其向下移动以维护堆属性
    private void heapifyDown(int index) {
        int leftChildIndex = 2 * index + 1;
        int rightChildIndex = 2 * index + 2;
        int largestIndex = index; // 假设当前节点最大

        // 检查左子节点
        if (leftChildIndex < heap.size() && heap.get(leftChildIndex) > heap.get(largestIndex)) {
            largestIndex = leftChildIndex;
        }

        // 检查右子节点
        if (rightChildIndex < heap.size() && heap.get(rightChildIndex) > heap.get(largestIndex)) {
            largestIndex = rightChildIndex;
        }

        // 如果最大值不是当前节点，则交换并继续下沉
        if (largestIndex != index) {
            swap(index, largestIndex);
            heapifyDown(largestIndex);
        }
    }

    // 交换两个位置的元素
    private void swap(int i, int j) {
        int temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }

    // 用于调试，打印堆内容
    public void printHeap() {
        System.out.println(heap.toString());
    }
}

public class HeapSort {

    // 堆排序主方法
    public static void sort(int[] arr) {
        int n = arr.length;

        // 1. 构建大顶堆（从最后一个非叶子节点开始向上heapify）
        // 最后一个非叶子节点的索引是 (n/2 - 1)
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 2. 逐个提取元素进行排序
        for (int i = n - 1; i > 0; i--) {
            // 将当前最大元素（堆顶）与当前堆的最后一个元素交换
            swap(arr, 0, i);
            // 对剩余的元素（不包括已排序的元素）重新进行堆化
            heapify(arr, i, 0); // 注意这里的n变成了i，表示堆的有效大小
        }
    }

    // 维护堆属性的下沉操作（与MaxHeap中的heapifyDown类似，但操作的是数组）
    private static void heapify(int[] arr, int n, int i) {
        int largest = i; // 初始化最大元素为根节点
        int left = 2 * i + 1; // 左子节点
        int 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);
        }
    }

    // 交换数组中两个元素的位置
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        // 测试MaxHeap
        System.out.println("--- MaxHeap 示例 ---");
        MaxHeap maxHeap = new MaxHeap();
        maxHeap.insert(3);
        maxHeap.insert(2);
        maxHeap.insert(15);
        maxHeap.insert(5);
        maxHeap.insert(4);
        maxHeap.insert(45);
        maxHeap.printHeap(); // 应该看到一个符合大顶堆特性的数组表示

        System.out.println("提取最大值: " + maxHeap.extractMax()); // 45
        maxHeap.printHeap();

        System.out.println("提取最大值: " + maxHeap.extractMax()); // 15
        maxHeap.printHeap();

        // 测试HeapSort
        System.out.println("\n--- 堆排序示例 ---");
        int[] data = {12, 11, 13, 5, 6, 7};
        System.out.println("原始数组: " + java.util.Arrays.toString(data));
        HeapSort.sort(data);
        System.out.println("排序后数组: " + java.util.Arrays.toString(data));

        int[] data2 = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
        System.out.println("原始数组2: " + java.util.Arrays.toString(data2));
        HeapSort.sort(data2);
        System.out.println("排序后数组2: " + java.util.Arrays.toString(data2));
    }
}

java.util.PriorityQueue

heapifyUp

heapifyDown

heapifyUp

heapifyDown