Java数据结构之最小堆和最大堆的原理及实现详解

什么是堆？

堆是一种特殊的树形数据结构，它满足以下两个条件：

• 堆是一个完全二叉树，即除了最后一层，其他层都必须填满，最后一层从左到右填满
• 堆中每个节点的值必须满足某种特定的条件，例如最小堆要求每个节点的值都小于等于其子节点的值。

堆一般分为两种类型：最小堆和最大堆。

最小堆：每个节点的值都小于等于其子节点的值。根节点是堆中最小的元素。

最大堆：每个节点的值都大于等于其子节点的值。根节点是堆中最大的元素。

堆结构用于解决从一堆元素中获取一组高（或低）优先级元素的场景，例如堆排序、优先队列、最短路径等。

最小堆和最大堆的实现

下面我们将介绍如何实现最小堆和最大堆。

最小堆的实现

最小堆中，每个节点的值都小于等于其子节点的值。本实例中我们将实现插入元素，删除最小元素和更新元素等基本操作。

首先，我们定义最小堆的属性和方法：

class MinHeap {
    private int[] heap;    // 堆数组
    private int size;      // 堆中元素个数
    private int maxSize;   // 堆可以容纳的最大元素个数

    // 构造方法
    public MinHeap(int maxSize) {
        this.maxSize = maxSize;
        heap = new int[maxSize];
        size = 0;
    }

    // 获取父节点的下标
    private int getParent(int pos) {
        return (pos - 1) / 2;
    }

    // 获取左子节点的下标
    private int getLeftChild(int pos) {
        return 2 * pos + 1;
    }

    // 获取右子节点的下标
    private int getRightChild(int pos) {
        return 2 * pos + 2;
    }
}

然后，我们实现插入操作：

// 插入元素
public void insert(int value) {
    if (size == maxSize) {
        System.out.println("Heap is full");
        return;
    }
    // 加入新元素
    heap[size++] = value;
    int current = size - 1;
    // 将新元素移至其合适位置
    while (current != 0 && heap[current] < heap[getParent(current)]) {
        swap(current, getParent(current));
        current = getParent(current);
    }
}

插入一个元素时，我们将其添加到下一个空闲位置，并将其移至合适位置，即比父节点元素小。

现在，我们实现删除操作：

// 删除最小元素
public int extractMin() {
    if (size <= 0) {
        System.out.println("Heap is empty");
        return Integer.MAX_VALUE;
    }
    int minElement = heap[0];
    // 将最后一个元素置为根节点
    heap[0] = heap[size - 1];
    size--;
    // 移至合适位置
    minHeapify(0);
    return minElement;
}

private void minHeapify(int pos) {
    int left = getLeftChild(pos);
    int right = getRightChild(pos);
    int smallest = pos;

    // 找到最小元素的下标
    if (left < size && heap[left] < heap[smallest]) {
        smallest = left;
    }

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

    // 如果最小元素的下标不是根节点的下标，则交换元素
    if (smallest != pos) {
        swap(pos, smallest);
        minHeapify(smallest);
    }
}

删除最小元素时，我们将堆中最后一个元素移至根节点的位置，然后自顶向下调整堆，保证最小堆的性质不被破坏。

最后，我们实现更新操作：

// 更新元素的值
public void decreaseKey(int pos, int newValue) {
    heap[pos] = newValue;
    while (pos != 0 && heap[pos] < heap[getParent(pos)]) {
        swap(pos, getParent(pos));
        pos = getParent(pos);
    }
}

更新操作将一个元素的值降低，我们将其移至合适位置，即比父节点元素小。

最大堆的实现

最大堆中，每个节点的值都大于等于其子节点的值。我们可以将最小堆的实现稍作改动，就可以得到最大堆。

首先，我们定义最大堆的属性和方法：

class MaxHeap {
    private int[] heap;    // 堆数组
    private int size;      // 堆中元素个数
    private int maxSize;   // 堆可以容纳的最大元素个数

    // 构造方法
    public MaxHeap(int maxSize) {
        this.maxSize = maxSize;
        heap = new int[maxSize];
        size = 0;
    }

    // 获取父节点的下标
    private int getParent(int pos) {
        return (pos - 1) / 2;
    }

    // 获取左子节点的下标
    private int getLeftChild(int pos) {
        return 2 * pos + 1;
    }

    // 获取右子节点的下标
    private int getRightChild(int pos) {
        return 2 * pos + 2;
    }
}

然后，我们实现插入操作：

// 插入元素
public void insert(int value) {
    if (size == maxSize) {
        System.out.println("Heap is full");
        return;
    }
    // 加入新元素
    heap[size++] = value;
    int current = size - 1;
    // 将新元素移至其合适位置
    while (current != 0 && heap[current] > heap[getParent(current)]) {
        swap(current, getParent(current));
        current = getParent(current);
    }
}

插入一个元素时，我们将其添加到下一个空闲位置，并将其移至合适位置，即比父节点元素大。

现在，我们实现删除操作：

// 删除最大元素
public int extractMax() {
    if (size <= 0) {
        System.out.println("Heap is empty");
        return Integer.MIN_VALUE;
    }
    int maxElement = heap[0];
    // 将最后一个元素置为根节点
    heap[0] = heap[size - 1];
    size--;
    // 移至合适位置
    maxHeapify(0);
    return maxElement;
}

private void maxHeapify(int pos) {
    int left = getLeftChild(pos);
    int right = getRightChild(pos);
    int largest = pos;

    // 找到最大元素的下标
    if (left < size && heap[left] > heap[largest]) {
        largest = left;
    }

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

    // 如果最大元素的下标不是根节点的下标，则交换元素
    if (largest != pos) {
        swap(pos, largest);
        maxHeapify(largest);
    }
}

删除最大元素时，我们将堆中最后一个元素移至根节点的位置，然后自顶向下调整堆，保证最大堆的性质不被破坏。

最后，我们实现更新操作：

// 更新元素的值
public void increaseKey(int pos, int newValue) {
    heap[pos] = newValue;
    while (pos != 0 && heap[pos] > heap[getParent(pos)]) {
        swap(pos, getParent(pos));
        pos = getParent(pos);
    }
}

更新操作将一个元素的值增加，我们将其移至合适位置，即比父节点元素大。

示例说明

示例1

下面我们将举一个例子以说明最小堆和最大堆的使用方法。

假设我们要从一堆数中找出前k个最大的数，我们可以使用最小堆实现。先将k个数插入最小堆中，然后对于每个数n，如果n比堆中最小的数要大，则将堆中最小的数删除，将n插入堆中。这样最后堆中的k个数就是要求的前k个最大数。

代码如下：

public static List<Integer> findKMax(int[] nums, int k) {
    MinHeap minHeap = new MinHeap(k);
    for (int i = 0; i < nums.length; i++) {
        if (i < k) {
            minHeap.insert(nums[i]);
        } else {
            if (nums[i] > minHeap.getMin()) {
                minHeap.extractMin();
                minHeap.insert(nums[i]);
            }
        }
    }
    return minHeap.getHeapList();
}

示例2

下面我们将再举一个例子以说明最大堆的使用方法。

假设我们要在一个大小为n的数组中查找第k大的元素，我们可以使用最大堆实现。将前k个元素插入最大堆中，然后对于从第k+1个元素到第n个元素，如果该元素比堆中最大的数要小，则将堆中最大的数删除，将该元素插入堆中。这样最终堆中的最大元素就是所求的Top k。

代码如下：

public static int findKthLargest(int[] nums, int k) {
    MaxHeap maxHeap = new MaxHeap(k);
    for (int i = 0; i < nums.length; i++) {
        if (i < k) {
            maxHeap.insert(nums[i]);
        } else {
            if (nums[i] < maxHeap.getMax()) {
                maxHeap.extractMax();
                maxHeap.insert(nums[i]);
            }
        }
    }
    return maxHeap.getMax();
}

总结

本文介绍了最小堆和最大堆的原理和实现。最小堆和最大堆是常用的数据结构之一，可用于解决各种算法问题。开发人员可以根据自己的需求，选择合适的堆结构进行实现。