数据结构第16节 最大堆

最大堆是一种特殊的完全二叉树数据结构，其中每个父节点的键值都大于或等于其子节点的键值。在Java中，最大堆通常用于实现优先队列，堆排序算法，或者在需要快速访问最大元素的应用场景中。

让我们通过一个具体的案例来说明最大堆的使用和实现：假设我们正在开发一个系统，用于实时分析用户行为数据，比如网站上的点击率。系统需要持续地接收点击事件，并能够快速报告过去一段时间内最高点击率的前N个页面。

实现最大堆

为了实现这个功能，我们可以使用最大堆来保存页面的点击率，堆顶元素总是保持为当前观察窗口内的最高点击率页面。当有新的点击事件到来时，我们将更新堆以反映最新的状态。

步骤：

1. 初始化堆：创建一个最大堆，可以使用数组来实现。堆中第一个元素（索引1，因为索引0通常不使用）是堆顶，也就是当前最大值。

2. 添加元素：当接收到新的点击事件时，将页面和其点击率插入堆中。为了保持堆的性质，需要执行“上浮”操作，即新插入的元素与其父节点比较，如果比父节点大，则交换它们的位置，继续向上比较直到满足堆的性质为止。

3. 删除元素：当需要移除堆顶元素（即最大点击率的页面）时，用堆的最后一个元素替换堆顶元素，然后执行“下沉”操作，比较该元素与其子节点，如果子节点中有更大的，则与最大的子节点交换位置，继续向下比较直到满足堆的性质为止。

4. 查询最大元素：堆顶元素始终是最大元素，可以直接访问而不影响堆的结构。

示例

下面是一个简单的最大堆实现示例，用于存储整数值：

public class MaxHeap {private int[] heap;private int size;public MaxHeap(int capacity) {heap = new int[capacity + 1]; // Index 0 is not usedsize = 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}
}

在这个案例中，我们创建了一个最大堆并插入了一些元素，然后提取了最大值。这只是一个基础的实现，实际应用中可能需要考虑更多的边界情况和异常处理。

在之前的示例中，我们创建了一个基本的最大堆数据结构。现在，我们将进一步完善这个数据结构，使其更加健壮和实用，包括添加更多功能和错误处理机制。

完善最大堆数据结构

1. 增加堆的动态扩容能力：当堆满时自动扩容。
2. 添加获取堆大小的方法：方便外部了解堆的状态。
3. 增强错误处理：在堆为空或满时抛出更有描述性的异常。
4. 添加完整打印堆的方法：便于调试和验证。

更新后的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 usedthis.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 30maxHeap.printHeap(); // Print the current state of the heaptry {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}
}

在这个更新的版本中，我们增加了堆的动态扩容能力，提供了获取堆大小的方法，增强了错误处理，并添加了打印堆的方法，使最大堆成为一个更完整、更健壮的数据结构。

既然我们已经建立了一个基本的最大堆，现在我们可以进一步完善它，添加更多的实用功能和优化点，比如：

1. 添加构建最大堆的方法：允许从一个数组快速构建最大堆。
2. 增加堆排序功能：利用最大堆进行排序。
3. 优化扩容策略：使用更高效的扩容策略。
4. 添加清除堆中所有元素的方法：重置堆到初始状态。
5. 增加查看但不移除最大值的方法：类似于队列的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 40System.out.println("Extracted max value: " + maxHeap.extractMax()); // Should print 40System.out.println("New maximum value: " + maxHeap.peekMax()); // Should print 30System.out.println("Sorted list: " + maxHeap.sort()); // Should print [30, 20, 15, 10]}
}

在这个版本中，我们使用了ArrayList代替原始数组，允许动态添加和移除元素，同时提供了构建最大堆、堆排序、查看最大值而不移除等功能，使得最大堆更加通用和强大。