Java 数据结构之堆的概念与应用

堆的概念

在计算机科学中，堆（Heap）是一种特殊的数据结构，是一棵树，每个父节点的键值都小于其子节点的键值，这样的堆成为小根堆（Min Heap），反之成为大根堆（Max Heap）。在堆中没有父子关系的节点之间也没有其他约束关系。常见的堆有二叉堆、斐波那契堆等。

对于小顶堆，任意节点的键值都小于或等于其子节点的键值，根节点的键值最小，可以用于实现优先队列（Priority Queue），时间复杂度为logN。

堆的应用

二叉堆

二叉堆是堆的一种常见而简单的实现，它可以用来实现堆栈（Heap Stack）和优先队列（Heap Priority Queue）。二叉堆分为最大堆和最小堆两种。

最大堆

在最大堆中，任何一个父节点的值都大于或等于其左右子节点的值，即根节点的值最大。

Java中的PriorityQueue就是一种基于最大堆的实现，可以通过以下代码创建：

PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());

最小堆

在最小堆中，任何一个父节点的值都小于或等于其左右子节点的值，即根节点的值最小。

可以通过以下代码创建：

PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();

堆排序

堆排序是一种原地排序算法，基于二叉堆实现。具体步骤如下：

1. 将要排序的数组构造成二叉堆
2. 将堆顶元素与堆底元素交换
3. 重新构造二叉堆，并重复步骤2，直到整个数组排序完成

Java实现代码如下：

public static void heapSort(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);
    }
}

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) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

示例说明

下面通过一个示例，说明堆的应用和使用：

假设有一个数组，我们需要找到其中第K大的数，可以通过构造一个小根堆，遍历数组将元素加入到堆中，并控制堆的大小不超过K，遍历完成后堆顶元素即为第K大的数。

代码如下：

public static int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> pQueue = new PriorityQueue<Integer>();
    for(int i=0; i<nums.length; i++) {
        pQueue.offer(nums[i]);
        if(pQueue.size() > k) {
            pQueue.poll();
        }
    }
    return pQueue.peek();
}

另一个示例是使用堆排序对数组进行排序，代码如下：

int[] arr = new int[]{7, 3, 5, 2, 6, 1, 4};
heapSort(arr);
System.out.println(Arrays.toString(arr));

输出结果为[1, 2, 3, 4, 5, 6, 7]。