最大堆 概述
最大堆是一种完全二叉树，其中每个内部节点的值都大于或等于其子节点的值。将堆的元素映射到数组中是非常直观的：如果一个节点存储在索引 k 处，那么它的左子节点存储在索引 2k + 1 处，右子节点存储在索引 2k + 2 处。
图示： 最大堆
最大堆是如何表示的？
最大堆是一棵完全二叉树。它通常表示为一个数组。根元素将位于 Arr[0]。下表显示了第 i个 节点（即 Arr[i]）的其他节点的索引：
> Arr[(i-1)/2] 返回父节点。
> Arr[(2*i)+1] 返回左子节点。
> Arr[(2*i)+2] 返回右子节点。
最大堆的操作如下：
- getMax(): 它返回最大堆的根元素。此操作的时间复杂度是 O(1)。
- extractMax(): 从最大堆中移除最大元素。此操作的时间复杂度是 O(Log n)，因为在移除根节点后，需要调用 堆化方法 来维护堆的性质。
- insert(): 插入一个新的键需要 O(Log n) 的时间。我们在树的末尾添加一个新键。如果新键比其父节点小，那么我们不需要做任何事。否则，我们需要向上遍历以修复被破坏的堆性质。
> 注意： 在下面的实现中，为了简化实现，我们从索引 1 开始进行索引。
实现方法：
我们可以通过以下列出的 2 种方法来实现目标：
- 通过创建 maxHeapify() 方法来实现的基本方法
- 通过库函数使用 Collections.reverseOrder() 方法
方法 1： 通过创建 maxHeapify() 方法来实现的基本方法
我们将创建一个方法，假设左右子树已经被堆化，我们只需要修复根节点。
示例
Java
// Java program to implement Max Heap
// Main class
public class MaxHeap {
private int[] Heap;
private int size;
private int maxsize;
// Constructor to initialize an
// empty max heap with given maximum
// capacity
public MaxHeap(int maxsize)
{
// This keyword refers to current instance itself
this.maxsize = maxsize;
this.size = 0;
Heap = new int[this.maxsize];
}
// Method 1
// Returning position of parent
private int parent(int pos) { return (pos – 1) / 2; }
// Method 2
// Returning left children
private int leftChild(int pos) { return (2 * pos) + 1; }
// Method 3
// Returning right children
private int rightChild(int pos)
{
return (2 * pos) + 2;
}
// Method 4
// Returning true if given node is leaf
private boolean isLeaf(int pos)
{
if (pos >= (size / 2) && pos < size) {
return true;
}
return false;
}
// Method 5
// Swapping nodes
private void swap(int fpos, int spos)
{
int tmp;
tmp = Heap[fpos];
Heap[fpos] = Heap[spos];
Heap[spos] = tmp;
}
// Method 6
// Recursive function to max heapify given subtree
private void maxHeapify(int pos)
{
if (isLeaf(pos))
return;
if (Heap[pos] < Heap[leftChild(pos)]
|| Heap[pos] < Heap[rightChild(pos)]) {
if (Heap[leftChild(pos)]
> Heap[rightChild(pos)]) {
swap(pos, leftChild(pos));
maxHeapify(leftChild(pos));
}
else {
swap(pos, rightChild(pos));
maxHeapify(rightChild(pos));
}
}
}
// Method 7
// Inserts a new element to max heap
public void insert(int element)
{
Heap[size] = element;
// Traverse up and fix violated property
int current = size;
while (Heap[current] > Heap[parent(current)]) {
swap(current, parent(current));
current = parent(current);
}
size++;
}
// Method 8
// To display heap
public void print()
{
for (int i = 0; i < size / 2; i++) {
System.out.print("Parent Node : " + Heap[i]);
if (leftChild(i)
< size) // if the child is out of the bound
// of the array
System.out.print(" Left Child Node: "
+ Heap[leftChild(i)]);
if (rightChild(i)
< size) // the right child index must not
// be out of the index of the array
System.out.print(" Right Child Node: "