java二叉堆,代码示例

Java二叉堆是一种特殊的二叉树数据结构，它满足堆属性：对于任意节点i，其父节点的值小于等于它的值。二叉堆常用于实现优先队列等数据结构，其中最小堆是最常见的一种。

在Java中，我们可以使用数组来表示二叉堆。对于任意节点i，其左子节点的索引为2*i+1，右子节点的索引为2*i+2，父节点的索引为(i-1)/2。通过这种方式，我们可以在数组中轻松地定位到任意节点的位置。

下面是一个简单的Java二叉堆的实现示例：

public class BinaryHeap {
    private int[] heap;
    private int size;
    public BinaryHeap(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;
        siftUp(size);
        size++;
    }
    public int extractMin() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        int min = heap[0];
        heap[0] = heap[size - 1];
        siftDown(0);
        size--;
        return min;
    }
    private void siftUp(int index) {
        int parentIndex = (index - 1) / 2;
        while (index > 0 && heap[index] < heap[parentIndex]) {
            swap(index, parentIndex);
            index = parentIndex;
            parentIndex = (index - 1) / 2;
        }
    }
    private void siftDown(int index) {
        int leftChildIndex = 2 * index + 1;
        int rightChildIndex = 2 * index + 2;
        int smallestIndex = index;
        if (leftChildIndex < size && heap[leftChildIndex] < heap[smallestIndex]) {
            smallestIndex = leftChildIndex;
        }
        if (rightChildIndex < size && heap[rightChildIndex] < heap[smallestIndex]) {
            smallestIndex = rightChildIndex;
        }
        if (smallestIndex != index) {
            swap(index, smallestIndex);
            siftDown(smallestIndex);
        }
    }
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

在上面的示例代码中，我们使用一个数组来存储二叉堆的元素，并使用一个变量`size`来记录当前堆的大小。`insert`方法用于向堆中插入一个元素，首先将元素放在数组的末尾，然后通过`siftUp`方法将其上浮到合适的位置。`extractMin`方法用于提取堆中的最小值，首先将根节点的值与数组末尾的值交换，然后通过`siftDown`方法将新的根节点下沉到合适的位置。

通过这种方式，我们可以方便地实现一个二叉堆，并且可以高效地进行插入和提取最小值的操作。