大顶堆（Max Heap）

大顶堆（Max Heap）

大顶堆是一种特殊的树形数据结构，它满足以下性质：

• 它是一个完全二叉树：除了最底层外，每一层都被完全填满。在最底层，所有的元素都应该尽可能地靠左排列。

• 每个节点的值都大于或等于其子节点的值。这就是为什么它被称为大顶堆。

下面是一个大顶堆的示例：

上图中，根节点（100）是所有节点中的最大值。同样，每个父节点的值都大于或等于其子节点的值。

好的，下面我将会分别介绍每个部分的代码：

定义变量

int[] array;
int size;

在这里，我们定义了两个成员变量。array 是用来存储堆中的元素的数组，size 是用来表示当前堆的大小。

构造函数

public MaxHeap(int[] array){
    this.array = array;
    this.size = array.length;
    heapify();
}

在构造函数中，我们初始化 array 和 size，并调用 heapify() 方法来构建大顶堆。

peek() 方法

public int peek(){
    if(size == 0)
        throw new IndexOutOfBoundsException();
    return array[0];
}

peek() 方法用于获取堆顶元素，也就是堆中的最大值。如果堆为空，则抛出 IndexOutOfBoundsException。

pool() 方法

public int pool(){
    return pool(0);
}

pool() 方法用于删除并返回堆顶元素。这个方法通过调用 pool(int index) 方法实现，参数为0，表示要删除的是堆顶元素。

pool(int index) 方法

public int pool(int index){
    if(index >= size){
        throw new IndexOutOfBoundsException();
    }
    int i = array[index];
    array[index] = array[size-1];
    size--;
    down(index);
    return i;
}

pool(int index) 方法用于删除指定索引位置的元素。首先，检查索引是否有效。然后，将要删除的元素保存在 i 中，将堆的最后一个元素移到该位置，并减小堆的大小。最后，调用 down(index) 方法调整堆的结构。

offer(int offered) 方法

public boolean offer(int offered){
    if (size == array.length)
        return false;
    up(offered);
    size++;
    return true;
}

offer(int offered) 方法用于向堆中添加一个元素。首先，检查堆是否已满。如果堆未满，将新元素添加到堆的末尾，并调用 up(offered) 方法调整堆的结构。

heapify() 方法

private void heapify(){
    for (int i = size/2 - 1; i >= 0; i--) {
        down(i);
    }
}

heapify() 方法用于将一个数组转换为大顶堆。从数组的一半开始（因为后一半的元素都是叶子节点，没有子节点），对每个元素调用 down(i) 方法。

up(int offered) 和 down(int parent) 方法

private void up(int offered){
    array[size] = offered;
    int child = size;
    int parent = (child - 1) / 2;
    while (child > 0){
        if(array[parent] > offered)
            return;
        change(parent,child);
        child = parent;
        parent = (child -1 ) /2;
    }
}

private void down(int parent){
    int child1 = parent * 2 + 1;
    int child2 = parent * 2 + 2;
    if(child1 >= size)
        return;
    int maxIndex = child2 < size && array[child2] > array[child1]
            ? child2:child1;
    if(array[parent] >= array[maxIndex])
        return;
    change(parent,maxIndex);
    down(maxIndex);
}

up(int offered) 和 down(int parent) 方法用于调整堆的结构。up(int offered) 方法在添加新元素时使用，它将新元素向上移动到正确的位置。down(int parent) 方法在删除元素或构建堆时使用，它将元素向下移动到正确的位置。

change(int parent,int child) 方法

private void change(int parent,int child){
    int i = array[parent];
    array[parent] = array[child];
    array[child] = i;
}

change(int parent,int child) 方法用于交换父节点和子节点的值。