最大堆、最小堆数据结构详细解读
最大堆、最小堆数据结构详细解读
堆是一种重要的数据结构,广泛应用于优先队列、排序算法、调度系统等场景。本文将详细介绍最大堆和最小堆的基本概念、核心操作及代码实现,并探讨它们在实际中的应用。
最大堆(Max Heap)与最小堆(Min Heap)
堆(Heap)是一种特殊的完全二叉树,它满足以下两个特性:
结构特性:堆必须是完全二叉树(Complete Binary Tree)。即除了最后一层之外,其他层都必须完全填满,且最后一层的节点从左向右连续排列。
堆特性:
最大堆(Max Heap):每个节点的值都大于或等于其子节点的值。
最小堆(Min Heap):每个节点的值都小于或等于其子节点的值。
堆广泛用于优先队列、排序算法(如堆排序)、调度系统等场景。下面是对最大堆和最小堆的详细介绍。
一、最大堆(Max Heap)
- 定义
最大堆是一种完全二叉树,满足堆特性:每个节点的值都大于或等于其子节点的值。
因此,堆顶元素(根节点)是整个堆中的最大值。
- 结构示意图
根节点 50 是堆中的最大值。
对于任意节点,其值都大于或等于其子节点的值。
- 核心操作
- 插入(Insert):
将新元素插入堆的最后一个位置。
通过上浮(Percolate Up)调整堆的顺序,直到满足堆特性。
- 删除最大元素(Extract Max):
取出堆顶元素(最大值)。
将堆的最后一个元素移动到堆顶。
通过下沉(Percolate Down)调整堆的顺序,直到满足堆特性。
代码实现(Java 示例)
import java.util.Arrays;
class MaxHeap {
private int[] heap;
private int size;
private int capacity;
public MaxHeap(int capacity) {
this.capacity = capacity;
heap = new int[capacity];
size = 0;
}
// 获取父节点索引
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 percolateUp(int index) {
while (index > 0 && heap[parent(index)] < heap[index]) {
swap(index, parent(index));
index = parent(index);
}
}
// 下沉操作
private void percolateDown(int index) {
int largest = index;
int left = leftChild(index);
int right = rightChild(index);
if (left < size && heap[left] > heap[largest]) {
largest = left;
}
if (right < size && heap[right] > heap[largest]) {
largest = right;
}
if (largest != index) {
swap(index, largest);
percolateDown(largest);
}
}
// 插入元素
public void insert(int value) {
if (size == capacity) throw new RuntimeException("Heap is full");
heap[size] = value;
size++;
percolateUp(size - 1);
}
// 删除最大元素
public int extractMax() {
if (size == 0) throw new RuntimeException("Heap is empty");
int max = heap[0];
heap[0] = heap[size - 1];
size--;
percolateDown(0);
return max;
}
// 交换元素
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.copyOfRange(heap, 0, size)));
}
}
public class MaxHeapTest {
public static void main(String[] args) {
MaxHeap maxHeap = new MaxHeap(10);
maxHeap.insert(50);
maxHeap.insert(30);
maxHeap.insert(20);
maxHeap.insert(15);
maxHeap.insert(10);
maxHeap.insert(5);
maxHeap.insert(8);
maxHeap.printHeap(); // 输出: [50, 30, 20, 15, 10, 5, 8]
System.out.println("Extract Max: " + maxHeap.extractMax()); // 输出: 50
maxHeap.printHeap(); // 输出: [30, 15, 20, 8, 10, 5]
}
}
- 时间复杂度
插入操作:O(logn)
删除最大元素:O(logn)
查找最大元素:O(1)
二、最小堆(Min Heap)
- 定义
最小堆是一种完全二叉树,满足堆特性:每个节点的值都小于或等于其子节点的值。
因此,堆顶元素(根节点)是整个堆中的最小值。
- 结构示意图
根节点 5 是堆中的最小值。
对于任意节点,其值都小于或等于其子节点的值。
- 核心操作
- 插入(Insert):
将新元素插入堆的最后一个位置。
通过上浮(Percolate Up)调整堆的顺序,直到满足堆特性。
- 删除最小元素(Extract Min):
取出堆顶元素(最小值)。
将堆的最后一个元素移动到堆顶。
通过下沉(Percolate Down)调整堆的顺序,直到满足堆特性。
代码实现(Java 示例)
class MinHeap {
private int[] heap;
private int size;
private int capacity;
public MinHeap(int capacity) {
this.capacity = capacity;
heap = new int[capacity];
size = 0;
}
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 percolateUp(int index) {
while (index > 0 && heap[parent(index)] > heap[index]) {
swap(index, parent(index));
index = parent(index);
}
}
private void percolateDown(int index) {
int smallest = index;
int left = leftChild(index);
int right = rightChild(index);
if (left < size && heap[left] < heap[smallest]) {
smallest = left;
}
if (right < size && heap[right] < heap[smallest]) {
smallest = right;
}
if (smallest != index) {
swap(index, smallest);
percolateDown(smallest);
}
}
public void insert(int value) {
if (size == capacity) throw new RuntimeException("Heap is full");
heap[size] = value;
size++;
percolateUp(size - 1);
}
public int extractMin() {
if (size == 0) throw new RuntimeException("Heap is empty");
int min = heap[0];
heap[0] = heap[size - 1];
size--;
percolateDown(0);
return min;
}
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
}
- 时间复杂度
插入操作:O(logn)
删除最小元素:O(logn)
查找最小元素:O(1)
三、最大堆与最小堆的应用
数据结构 | 应用场景 |
---|---|
最大堆 | 优先队列(最大优先级)、实时数据流中的第 K 大元素 |
最小堆 | 优先队列(最小优先级)、Dijkstra 最短路径算法 |
堆的特性使其在许多场景下非常有用,如调度系统、事件模拟、动态中位数维护等。