Java实现大根堆与小根堆详解

定义

大根堆是一种特殊的完全二叉树，其中每个父节点的值都大于或等于其左右子节点的值。使用数组实现时，我们可以通过索引关系来表示节点间的父子关系：

• 对于索引为 i 的节点，其父节点索引为 (i-1)/2
• 左子节点索引为 2i+1
• 右子节点索引为 2i+2

最大堆和最小堆的关键操作有2种：插入元素、获取堆顶元素

插入元素的思路

       放到数组的末尾，执行上浮操作

获取堆顶元素的思路

        移除堆顶元素后，把数组末尾的元素放在堆顶，执行下沉操作

最大堆java实现

import java.util.Arrays;public class MaxHeap {private int[] heap; // 存储堆元素的数组private int size;   // 当前堆中元素的数量private int capacity; // 堆的容量// 构造函数，初始化指定容量的堆public MaxHeap(int capacity) {this.capacity = capacity;this.size = 0;this.heap = new int[capacity];}// 获取堆的大小public int size() {return size;}// 判断堆是否为空public boolean isEmpty() {return size == 0;}// 插入元素public void insert(int value) {if (size == capacity) {throw new IllegalStateException("堆已满，无法插入新元素");}// 将新元素添加到数组末尾heap[size] = value;size++;// 执行上浮操作，维持大根堆性质siftUp(size - 1);}// 弹出堆顶元素（最大值）public int pop() {if (isEmpty()) {throw new IllegalStateException("堆为空，无法弹出元素");}// 保存堆顶元素int maxValue = heap[0];// 将最后一个元素移到堆顶heap[0] = heap[size - 1];size--;// 执行下沉操作，维持大根堆性质siftDown(0);return maxValue;}// 上浮操作：当插入新元素时，将其向上调整到合适位置private void siftUp(int index) {// 只要不是根节点且当前节点大于父节点，就交换位置while (index > 0 && heap[index] > heap[parent(index)]) {swap(index, parent(index));index = parent(index);}}// 下沉操作：当移除堆顶元素后，将新的堆顶元素向下调整到合适位置private void siftDown(int index) {// 循环直到当前节点是叶子节点或满足大根堆性质while (true) {int left = leftChild(index);int right = rightChild(index);int largest = index; // 假设当前节点是最大的// 比较左子节点if (left < size && heap[left] > heap[largest]) {largest = left;}// 比较右子节点if (right < size && heap[right] > heap[largest]) {largest = right;}// 如果当前节点已是最大，则无需继续下沉if (largest == index) {break;}// 交换当前节点与最大子节点的位置swap(index, largest);index = largest;}}// 获取父节点索引private int parent(int index) {return (index - 1) / 2;}// 获取左子节点索引private int leftChild(int index) {return 2 * index + 1;}// 获取右子节点索引private int rightChild(int index) {return 2 * index + 2;}// 交换两个索引位置的元素private void swap(int i, int j) {int temp = heap[i];heap[i] = heap[j];heap[j] = temp;}// 打印堆中的元素public void printHeap() {System.out.println(Arrays.toString(Arrays.copyOf(heap, size)));}// 测试代码public static void main(String[] args) {MaxHeap heap = new MaxHeap(10);// 插入元素heap.insert(10);heap.insert(20);heap.insert(5);heap.insert(30);heap.insert(15);System.out.println("插入元素后的堆:");heap.printHeap(); // 应该输出 [30, 20, 5, 10, 15]// 弹出元素System.out.println("弹出的最大值: " + heap.pop()); // 30System.out.println("弹出后堆的状态:");heap.printHeap(); // 应该输出 [20, 15, 5, 10]heap.insert(25);System.out.println("插入25后的堆:");heap.printHeap(); // 应该输出 [25, 15, 5, 10, 20]}
}

最小堆java实现

import java.util.Arrays;public class MinHeap {private int[] heap;   // 存储堆元素的数组private int size;     // 当前堆中元素的数量private int capacity; // 堆的容量// 构造函数，初始化指定容量的堆public MinHeap(int capacity) {this.capacity = capacity;this.size = 0;this.heap = new int[capacity];}// 获取堆的大小public int size() {return size;}// 判断堆是否为空public boolean isEmpty() {return size == 0;}// 插入元素public void insert(int value) {if (size == capacity) {throw new IllegalStateException("堆已满，无法插入新元素");}// 将新元素添加到数组末尾heap[size] = value;size++;// 执行上浮操作，维持小根堆性质siftUp(size - 1);}// 弹出堆顶元素（最小值）public int pop() {if (isEmpty()) {throw new IllegalStateException("堆为空，无法弹出元素");}// 保存堆顶元素int minValue = heap[0];// 将最后一个元素移到堆顶heap[0] = heap[size - 1];size--;// 执行下沉操作，维持小根堆性质siftDown(0);return minValue;}// 上浮操作：当插入新元素时，将其向上调整到合适位置private void siftUp(int index) {// 只要不是根节点且当前节点小于父节点，就交换位置while (index > 0 && heap[index] < heap[parent(index)]) {swap(index, parent(index));index = parent(index);}}// 下沉操作：当移除堆顶元素后，将新的堆顶元素向下调整到合适位置private void siftDown(int index) {// 循环直到当前节点是叶子节点或满足小根堆性质while (true) {int left = leftChild(index);int right = rightChild(index);int smallest = index; // 假设当前节点是最小的// 比较左子节点if (left < size && heap[left] < heap[smallest]) {smallest = left;}// 比较右子节点if (right < size && heap[right] < heap[smallest]) {smallest = right;}// 如果当前节点已是最小，则无需继续下沉if (smallest == index) {break;}// 交换当前节点与最小子节点的位置swap(index, smallest);index = smallest;}}// 获取父节点索引private int parent(int index) {return (index - 1) / 2;}// 获取左子节点索引private int leftChild(int index) {return 2 * index + 1;}// 获取右子节点索引private int rightChild(int index) {return 2 * index + 2;}// 交换两个索引位置的元素private void swap(int i, int j) {int temp = heap[i];heap[i] = heap[j];heap[j] = temp;}// 打印堆中的元素public void printHeap() {System.out.println(Arrays.toString(Arrays.copyOf(heap, size)));}// 测试代码public static void main(String[] args) {MinHeap heap = new MinHeap(10);// 插入元素heap.insert(10);heap.insert(20);heap.insert(5);heap.insert(30);heap.insert(15);System.out.println("插入元素后的堆:");heap.printHeap(); // 应该输出 [5, 10, 20, 30, 15]// 弹出元素System.out.println("弹出的最小值: " + heap.pop()); // 5System.out.println("弹出后堆的状态:");heap.printHeap(); // 应该输出 [10, 15, 20, 30]heap.insert(3);System.out.println("插入3后的堆:");heap.printHeap(); // 应该输出 [3, 10, 20, 30, 15]}
}

空间复杂度

• 整体空间复杂度：O (n)，其中 n 是堆的容量
  • 主要占用空间的是存储堆元素的数组heap，其大小为堆的容量
  • 其他变量（size、capacity 等）占用常数空间 O (1)

时间复杂度分析

1. 插入操作（insert）

   • 时间复杂度：O (log n)
   • 分析：插入元素后可能需要执行上浮操作（siftUp），最多需要比较和交换的次数等于堆的高度。对于包含 n 个元素的完全二叉树，高度为 log₂n，因此时间复杂度为 O (log n)

2. 弹出操作（pop）

   • 时间复杂度：O (log n)
   • 分析：弹出堆顶元素后需要执行下沉操作（siftDown），最多需要比较和交换的次数等于堆的高度，即 log₂n，因此时间复杂度为 O (log n)

3. 构建堆操作（buildMinHeap）

   • 时间复杂度：O (n)
   • 分析：这个结果可能有点反直觉，虽然我们对每个非叶子节点执行了下沉操作（O (log n)），但实际上整体复杂度是线性的。
   • 具体推导：对于高度为 h 的节点，最多需要下沉 h 次。堆中高度为 h 的节点数量最多为 n/(2ʰ⁺¹)，整体操作次数为 O (n)

4. 辅助操作

   • parent ()、leftChild ()、rightChild ()：O (1)，仅进行简单的算术计算
   • swap ()：O (1)，仅进行常数次元素交换
   • size ()、isEmpty ()：O (1)，仅返回或判断变量值