大顶堆（Max Heap）

本文主要是介绍大顶堆（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) 方法用于交换父节点和子节点的值。

这篇关于大顶堆（Max Heap）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---