Java 中的堆数据结构158

简介

堆是一种树状数据结构，其中每个节点都大于或等于其子节点。堆通常用于优先级队列，即需要按照特定顺序（通常按值排序）访问元素的队列。

实现

在 Java 中，堆通常使用数组实现。数组中的每个元素都对应于堆中的一个节点，根节点位于数组索引 0 处。左子节点位于索引 2*i 处，右子节点位于索引 2*i+1 处，其中 i 是父节点的索引。

为了维护堆的性质，当一个新元素被插入或一个元素被删除时，需要对堆进行调整。插入操作包括将新元素添加到数组末尾，然后向上堆化，即将新元素与其父节点比较，如果大于父节点，则交换两个元素的位置。

删除操作包括将根节点替换为数组中的最后一个元素，然后向下堆化，即将根节点与较大的子节点比较，如果小于子节点，则交换两个元素的位置。此过程一直持续到根节点大于等于其两个子节点。

代码示例

以下 Java 代码演示了如何使用数组实现堆：```java
public class Heap {
private int[] heap;
private int size;
public Heap(int capacity) {
= new int[capacity];
}
public void insert(int value) {
if (size == ) {
throw new IndexOutOfBoundsException();
}
heap[size] = value;
upheap(size);
size++;
}
private void upheap(int index) {
while (index > 0) {
int parentIndex = (index - 1) / 2;
if (heap[index] > heap[parentIndex]) {
swap(index, parentIndex);
}
index = parentIndex;
}
}
public int remove() {
if (size == 0) {
throw new IndexOutOfBoundsException();
}
int value = heap[0];
heap[0] = heap[size - 1];
size--;
downheap(0);
return value;
}
private void downheap(int index) {
while (index < size) {
int leftChildIndex = 2 * index + 1;
int rightChildIndex = 2 * index + 2;
int maxChildIndex = -1;
if (leftChildIndex < size && heap[leftChildIndex] > heap[index]) {
maxChildIndex = leftChildIndex;
}
if (rightChildIndex < size && heap[rightChildIndex] > heap[maxChildIndex]) {
maxChildIndex = rightChildIndex;
}
if (maxChildIndex == -1) {
break;
}
swap(index, maxChildIndex);
index = maxChildIndex;
}
}
private void swap(int index1, int index2) {
int temp = heap[index1];
heap[index1] = heap[index2];
heap[index2] = temp;
}
}
```