Java 中堆的实现

简介

在计算机科学中，堆（Heap）是一种特殊的数据结构，它是一个完全二叉树，并且满足堆属性：每个节点的值都大于或等于其子节点的值（最大堆），或者每个节点的值都小于或等于其子节点的值（最小堆）。在 Java 中，堆的实现广泛应用于各种算法和数据处理场景，如优先队列、Dijkstra 算法等。本文将深入探讨在 Java 中如何实现堆，包括基础概念、使用方法、常见实践以及最佳实践。

目录

1. 堆的基础概念
2. Java 中堆的使用方法
   • 使用 PriorityQueue 类
   • 自定义堆实现
3. 常见实践
   • 堆排序
   • 实现优先队列
4. 最佳实践
   • 性能优化
   • 内存管理
5. 小结
6. 参考资料

堆的基础概念

堆是一种树形数据结构，具有以下特点： - 完全二叉树：除了最后一层，每一层的节点数都是满的，最后一层的节点从左到右填充。 - 堆属性： - 最大堆：父节点的值大于或等于其子节点的值。 - 最小堆：父节点的值小于或等于其子节点的值。

堆的存储通常使用数组，对于数组 heap，如果节点的索引为 i，则其左子节点的索引为 2 * i + 1，右子节点的索引为 2 * i + 2，父节点的索引为 (i - 1) / 2。

Java 中堆的使用方法

使用 PriorityQueue 类

Java 提供了 PriorityQueue 类，它是一个基于堆实现的优先队列。以下是一个简单的示例：

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 创建一个最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 向堆中添加元素
        minHeap.add(3);
        minHeap.add(1);
        minHeap.add(4);
        minHeap.add(1);
        minHeap.add(5);
        minHeap.add(9);

        // 从堆中取出元素，每次取出的是最小元素
        while (!minHeap.isEmpty()) {
            System.out.println(minHeap.poll());
        }
    }
}

自定义堆实现

有时候我们需要自定义堆的行为，比如实现一个最大堆。以下是一个自定义最大堆的示例：

import java.util.Comparator;

public class MaxHeap {
    private int[] heap;
    private int size;

    public MaxHeap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }

    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    private void heapifyUp(int index) {
        while (index > 0 && heap[(index - 1) / 2] < heap[index]) {
            swap((index - 1) / 2, index);
            index = (index - 1) / 2;
        }
    }

    private void heapifyDown(int index) {
        int largest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;

        if (left < size && heap[left] > heap[largest]) {
            largest = left;
        }

        if (right < size && heap[right] > heap[largest]) {
            largest = right;
        }

        if (largest != index) {
            swap(index, largest);
            heapifyDown(largest);
        }
    }

    public void add(int value) {
        if (size == heap.length) {
            throw new RuntimeException("Heap is full");
        }
        heap[size] = value;
        heapifyUp(size);
        size++;
    }

    public int poll() {
        if (size == 0) {
            throw new RuntimeException("Heap is empty");
        }
        int result = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown(0);
        return result;
    }

    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(10);
        maxHeap.add(3);
        maxHeap.add(1);
        maxHeap.add(4);
        maxHeap.add(1);
        maxHeap.add(5);
        maxHeap.add(9);

        while (maxHeap.size > 0) {
            System.out.println(maxHeap.poll());
        }
    }
}

常见实践

堆排序

堆排序是一种基于堆的数据结构的排序算法。以下是使用最大堆实现堆排序的示例：

public class HeapSort {
    private 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) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;

            heapify(arr, n, largest);
        }
    }

    public void sort(int[] arr) {
        int n = arr.length;

        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            heapify(arr, i, 0);
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9};
        HeapSort heapSort = new HeapSort();
        heapSort.sort(arr);

        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

实现优先队列

除了使用 PriorityQueue 类，我们也可以通过自定义堆来实现优先队列。示例代码如下：

import java.util.Comparator;

public class CustomPriorityQueue<T> {
    private T[] heap;
    private int size;
    private Comparator<T> comparator;

    public CustomPriorityQueue(int capacity, Comparator<T> comparator) {
        heap = (T[]) new Object[capacity];
        size = 0;
        this.comparator = comparator;
    }

    private void swap(int i, int j) {
        T temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    private void heapifyUp(int index) {
        while (index > 0 && comparator.compare(heap[(index - 1) / 2], heap[index]) > 0) {
            swap((index - 1) / 2, index);
            index = (index - 1) / 2;
        }
    }

    private void heapifyDown(int index) {
        int smallest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;

        if (left < size && comparator.compare(heap[left], heap[smallest]) < 0) {
            smallest = left;
        }

        if (right < size && comparator.compare(heap[right], heap[smallest]) < 0) {
            smallest = right;
        }

        if (smallest != index) {
            swap(index, smallest);
            heapifyDown(smallest);
        }
    }

    public void add(T value) {
        if (size == heap.length) {
            throw new RuntimeException("Queue is full");
        }
        heap[size] = value;
        heapifyUp(size);
        size++;
    }

    public T poll() {
        if (size == 0) {
            throw new RuntimeException("Queue is empty");
        }
        T result = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown(0);
        return result;
    }

    public static void main(String[] args) {
        CustomPriorityQueue<Integer> queue = new CustomPriorityQueue<>(10, (a, b) -> a - b);
        queue.add(3);
        queue.add(1);
        queue.add(4);
        queue.add(1);
        queue.add(5);
        queue.add(9);

        while (queue.size > 0) {
            System.out.println(queue.poll());
        }
    }
}

最佳实践

性能优化

• 减少不必要的操作：在堆的实现中，尽量减少不必要的比较和交换操作。例如，在 heapify 方法中，可以使用临时变量来存储较大或较小的值，减少数组访问次数。
• 使用合适的数据结构：根据具体需求选择合适的堆实现。如果需要频繁插入和删除操作，PriorityQueue 可能是一个不错的选择；如果对性能要求极高，可以考虑自定义堆实现。

内存管理

• 避免内存泄漏：在堆的实现中，确保及时释放不再使用的内存。例如，在删除元素时，将数组中对应的位置设为 null，以便垃圾回收器回收内存。
• 合理设置堆的大小：根据数据量的大小合理设置堆的初始容量，避免频繁的扩容操作，提高性能。

小结

本文详细介绍了在 Java 中堆的基础概念、使用方法、常见实践以及最佳实践。通过学习这些内容，读者可以深入理解堆的数据结构，并能够在实际开发中灵活运用堆来解决各种问题，如排序、实现优先队列等。

参考资料

• 《Effective Java》
• 《算法导论》