最大堆是一种特殊的完全二叉树数据结构，其中每个父节点的键值都大于或等于其子节点的键值。在Java中，最大堆通常用于实现优先队列，堆排序算法，或者在需要快速访问最大元素的应用场景中。
让我们通过一个具体的案例来说明最大堆的使用和实现：假设我们正在开发一个系统，用于实时分析用户行为数据，比如网站上的点击率。系统需要持续地接收点击事件，并能够快速报告过去一段时间内最高点击率的前N个页面。
实现最大堆
为了实现这个功能，我们可以使用最大堆来保存页面的点击率，堆顶元素总是保持为当前观察窗口内的最高点击率页面。当有新的点击事件到来时，我们将更新堆以反映最新的状态。
步骤：
-
初始化堆：创建一个最大堆，可以使用数组来实现。堆中第一个元素（索引1，因为索引0通常不使用）是堆顶，也就是当前最大值。
-
添加元素：当接收到新的点击事件时，将页面和其点击率插入堆中。为了保持堆的性质，需要执行“上浮”操作，即新插入的元素与其父节点比较，如果比父节点大，则交换它们的位置，继续向上比较直到满足堆的性质为止。
-
删除元素：当需要移除堆顶元素（即最大点击率的页面）时，用堆的最后一个元素替换堆顶元素，然后执行“下沉”操作，比较该元素与其子节点，如果子节点中有更大的，则与最大的子节点交换位置，继续向下比较直到满足堆的性质为止。
-
查询最大元素：堆顶元素始终是最大元素，可以直接访问而不影响堆的结构。
示例
下面是一个简单的最大堆实现示例，用于存储整数值：
public class MaxHeap {
private int[] heap;
private int size;
public MaxHeap(int capacity) {
heap = new int[capacity + 1]; // Index 0 is not used
size = 0;
}
public void insert(int value) {
if (size == heap.length - 1) {
throw new IllegalStateException("Heap is full");
}
size++;
heap[size] = value;
siftUp(size);
}
private void siftUp(int index) {
while (index > 1 && heap[index / 2] < heap[index]) {
swap(index, index / 2);
index /= 2;
}
}
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
public int extractMax() {
if (size == 0) {
throw new IllegalStateException("Heap is empty");
}
int max = heap[1];
heap[1] = heap[size];
size--;
siftDown(1);
return max;
}
private void siftDown(int index) {
while (index * 2 <= size) {
int child = index * 2;
if (child != size && heap[child] < heap[child + 1]) {
child++;
}
if (heap[index] >= heap[child]) {
break;
}
swap(index, child);
index = child;
}
}
}
使用
public class Main {
public static void main(String[] args) {
MaxHeap maxHeap = new MaxHeap(10);
maxHeap.insert(10);
maxHeap.insert(20);
maxHeap.insert(15);
maxHeap.insert(30);
System.out.println("Maximum value: " + maxHeap.extractMax()); // Should print 30
}
}
在这个案例中，我们创建了一个最大堆并插入了一些元素，然后提取了最大值。这只是一个基础的实现，实际应用中可能需要考虑更多的边界情况和异常处理。
在之前的示例中，我们创建了一个基本的最大堆数据结构。现在，我们将进一步完善这个数据结构，使其更加健壮和实用，包括添加更多功能和错误处理机制。
完善最大堆数据结构
- 增加堆的动态扩容能力：当堆满时自动扩容。
- 添加获取堆大小的方法：方便外部了解堆的状态。
- 增强错误处理：在堆为空或满时抛出更有描述性的异常。
- 添加完整打印堆的方法：便于调试和验证。
更新后的Java代码：
public class MaxHeap {
private int[] heap;
private int size;
private int capacity;
public MaxHeap(int initialCapacity) {
this.capacity = initialCapacity;
this.heap = new int[initialCapacity + 1]; // Index 0 is not used
this.size = 0;
}
public void insert(int value) {
ensureCapacity();
size++;
heap[size] = value;
siftUp(size);
}
private void ensureCapacity() {
if (size == heap.length - 1) {
int newCapacity = heap.length * 2;
heap = Arrays.copyOf(heap, newCapacity);
capacity = newCapacity - 1;
}
}
private void siftUp(int index) {
while (index > 1 && heap[index / 2] < heap[index]) {
swap(index, index / 2);
index /= 2;
}
}
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
public int extractMax() {
if (isEmpty()) {
throw new IllegalStateException("Heap is empty");
}
int max = heap[1];
heap[1] = heap[size];
size--;
siftDown(1);
return max;
}
private void siftDown(int index) {
while (index * 2 <= size) {
int child = index * 2;
if (child != size && heap[child] < heap[child + 1]) {
child++;
}
if (heap[index] >= heap[child]) {
break;
}
swap(index, child);
index = child;
}
}
public boolean isEmpty() {
return size == 0;
}
public int getSize() {
return size;
}
public void printHeap() {
for (int i = 1; i <= size; i++) {
System.out.print(heap[i] + " ");
}
System.out.println();
}
}
使用
public class Main {
public static void main(String[] args) {
MaxHeap maxHeap = new MaxHeap(10);
maxHeap.insert(10);
maxHeap.insert(20);
maxHeap.insert(15);
maxHeap.insert(30);
System.out.println("Maximum value: " + maxHeap.extractMax()); // Should print 30
maxHeap.printHeap(); // Print the current state of the heap
try {
maxHeap.extractMax();
maxHeap.extractMax();
maxHeap.extractMax();
maxHeap.extractMax();
maxHeap.extractMax(); // This should throw an exception since the heap is now empty
} catch (IllegalStateException e) {
System.out.println(e.getMessage());
}
System.out.println("Heap size: " + maxHeap.getSize()); // Should print 0
}
}
在这个更新的版本中，我们增加了堆的动态扩容能力，提供了获取堆大小的方法，增强了错误处理，并添加了打印堆的方法，使最大堆成为一个更完整、更健壮的数据结构。
既然我们已经建立了一个基本的最大堆，现在我们可以进一步完善它，添加更多的实用功能和优化点，比如：
- 添加构建最大堆的方法：允许从一个数组快速构建最大堆。
- 增加堆排序功能：利用最大堆进行排序。
- 优化扩容策略：使用更高效的扩容策略。
- 添加清除堆中所有元素的方法：重置堆到初始状态。
- 增加查看但不移除最大值的方法：类似于队列的peek操作。
更新后的最大堆Java代码：
public class MaxHeap<T extends Comparable<T>> {
private List<T> heap = new ArrayList<>();
public MaxHeap() {}
public MaxHeap(T[] items) {
heap.addAll(Arrays.asList(items));
buildHeap();
}
public void insert(T value) {
heap.add(value);
siftUp(heap.size() - 1);
}
private void siftUp(int index) {
while (index > 0 && heap.get(parent(index)).compareTo(heap.get(index)) < 0) {
swap(index, parent(index));
index = parent(index);
}
}
private void swap(int i, int j) {
T temp = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, temp);
}
public T extractMax() {
if (isEmpty()) {
throw new IllegalStateException("Heap is empty");
}
T max = heap.get(0);
heap.set(0, heap.get(heap.size() - 1));
heap.remove(heap.size() - 1);
siftDown(0);
return max;
}
private void siftDown(int index) {
int left = leftChild(index);
while (left < heap.size()) {
int right = rightChild(index);
int largest = (right < heap.size() && heap.get(right).compareTo(heap.get(left)) > 0) ? right : left;
largest = (heap.get(largest).compareTo(heap.get(index)) > 0) ? largest : index;
if (largest == index) {
break;
}
swap(index, largest);
index = largest;
left = leftChild(index);
}
}
public boolean isEmpty() {
return heap.isEmpty();
}
public int size() {
return heap.size();
}
public void clear() {
heap.clear();
}
public T peekMax() {
if (isEmpty()) {
throw new IllegalStateException("Heap is empty");
}
return heap.get(0);
}
public void buildHeap() {
for (int i = parent(heap.size() - 1); i >= 0; i--) {
siftDown(i);
}
}
private int parent(int i) {
return (i - 1) / 2;
}
private int leftChild(int i) {
return 2 * i + 1;
}
private int rightChild(int i) {
return 2 * i + 2;
}
public List<T> sort() {
List<T> sorted = new ArrayList<>();
while (!isEmpty()) {
sorted.add(extractMax());
}
return sorted;
}
}
使用方式：
public class Main {
public static void main(String[] args) {
Integer[] numbers = {10, 20, 15, 30, 40};
MaxHeap<Integer> maxHeap = new MaxHeap<>(numbers);
System.out.println("Maximum value: " + maxHeap.peekMax()); // Should print 40
System.out.println("Extracted max value: " + maxHeap.extractMax()); // Should print 40
System.out.println("New maximum value: " + maxHeap.peekMax()); // Should print 30
System.out.println("Sorted list: " + maxHeap.sort()); // Should print [30, 20, 15, 10]
}
}
在这个版本中，我们使用了ArrayList代替原始数组，允许动态添加和移除元素，同时提供了构建最大堆、堆排序、查看最大值而不移除等功能，使得最大堆更加通用和强大。