你作为一个Java领域的专家,请完成以下任务:堆的结构。
时间: 2023-12-14 07:38:29 浏览: 19
堆(Heap)是一种特殊的树形数据结构,它满足以下两个条件:
1. 堆总是一棵完全二叉树;
2. 堆中的每个节点都必须满足父节点的值大于或等于(最大堆)或小于或等于(最小堆)子节点的值。
堆可以用数组来实现。对于一个父节点的下标为i,它的左子节点的下标为2i+1,右子节点的下标为2i+2。可以使用数组来表示一个堆,其中数组中第一个元素即为根节点。
堆的操作有插入和删除。当向堆中插入一个元素时,先将元素插入到堆的底部,然后与其父节点进行比较,如果满足堆的性质,则不需要进行任何操作;否则,将该元素与其父节点交换,直到满足堆的性质。当从堆中删除一个元素时,先将堆顶元素取出,然后将堆底元素放到堆顶位置,再与其子节点进行比较,如果满足堆的性质,则不需要进行任何操作;否则,将该元素与其子节点中较大(最大堆)或较小(最小堆)的节点交换,直到满足堆的性质。
以下是一个最大堆的Java实现:
```java
public class MaxHeap {
private int[] heap;
private int size;
public MaxHeap(int capacity) {
heap = new int[capacity];
size = 0;
}
public void insert(int value) {
if (size == heap.length) {
throw new IllegalStateException("Heap is full");
}
heap[size] = value;
size++;
int index = size - 1;
while (index > 0 && heap[index] > heap[(index - 1) / 2]) {
swap(index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
public int delete() {
if (size == 0) {
throw new IllegalStateException("Heap is empty");
}
int deletedValue = heap[0];
heap[0] = heap[size - 1];
size--;
int index = 0;
while (index * 2 + 1 < size) {
int leftChild = index * 2 + 1;
int rightChild = index * 2 + 2;
int largerChild = leftChild;
if (rightChild < size && heap[rightChild] > heap[leftChild]) {
largerChild = rightChild;
}
if (heap[index] >= heap[largerChild]) {
break;
}
swap(index, largerChild);
index = largerChild;
}
return deletedValue;
}
private void swap(int i, int j) {
int tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;
}
}
```
使用示例:
```java
MaxHeap maxHeap = new MaxHeap(10);
maxHeap.insert(5);
maxHeap.insert(3);
maxHeap.insert(8);
maxHeap.insert(1);
maxHeap.insert(9);
System.out.println(maxHeap.delete()); // 输出9
System.out.println(maxHeap.delete()); // 输出8
```