Java中的最大堆数据结构实现
最大堆是完整的二叉树，其中节点的值大于或者等于其子代的值。
Max Heap数据结构对于使用堆排序对数据进行排序非常有用。
在本教程中，我们将介绍从头开始在Java中实现最大堆所需的所有知识。
Java中最大堆数据结构的实现
我们使用数组表示堆。
由于堆是完整的二叉树，因此不会浪费空间。
例如，让我们考虑如下的堆：
数组表示为：
最大堆的声明如下：
static class MaxHeap {
private int[] Heap; //array
private int size;
private int maxsize;
public MaxHeap(int size) {
this.maxsize = size;
this.size = 0;
Heap = new int[this.maxsize + 1];
Heap[0] = Integer.MAX_VALUE;
}
堆是存储最大堆的数组。
构造函数采用大小并将数组的第0个元素初始化为无穷大。
我们从索引1开始我们的堆。
1.获取节点的父节点
由于我们将堆存储为数组，因此获取节点的父节点变得更加容易。
对于位于位置i的元素，其父元素的位置由给出：
(i)/2
在实现过程中，我们可以使用以下方法获取父项：
private int parent(int pos) {
return pos/2;
}
2.为节点获取子代
对于位置i处的节点，其子级由以下公式给出：
左孩子：
(2*i)
合适的孩子：
(2*i)+ 1
注意：当堆从索引1开始时，这是正确的。
如果堆从位置0开始，则左子对象和右子对象的值分别为(2 * i)+1和(2 * i)+2。
在代码中，我们如下实现：
private int leftChild(int pos) {
return (2 * pos) ;
}
private int rightChild(int pos) {
return (2 * pos) + 1;
}
3.堆新插入的元素
将元素插入堆后，它可能不满足堆属性。
在这种情况下，我们需要调整堆的位置以使其再次成为堆。
此过程称为堆整。
要在最大堆中堆积一个元素，我们需要找到其最大子元素并将其与当前元素交换。
我们继续此过程，直到每个节点上的heap属性都满足为止。
为了堆积，我们从根部向下移动到叶子。
因此，这也称为Down Heapify。
另一个需要注意的有趣点是，我们仅在非叶节点上执行down heapify。
下堆函数的代码是：
private void downHeapify(int pos) {
//checking if the node is a leaf node
if (pos >= (size/2) && pos <= size)
return;
//checking if a swap is needed
if (Heap[pos] < Heap[leftChild(pos)] ||
Heap[pos] < Heap[rightChild(pos)]) {
//replacing parent with maximum of left and right child
if (Heap[leftChild(pos)] > Heap[rightChild(pos)]) {
swap(pos, leftChild(pos));
//after swaping, heapify is called on the children
downHeapify(leftChild(pos));
} else {
swap(pos, rightChild(pos));
//after swaping, heapify is called on the children
downHeapify(rightChild(pos));
}
}
}
交换函数如下：
private void swap(int fpos, int spos) {
int tmp;
tmp = Heap[fpos];
Heap[fpos] = Heap[spos];
Heap[spos] = tmp;
}
您也可以使用while循环而不是递归来编写相同的代码。
在低调处理中，我们从父母转向孩子。
我们也可以采用自下而上的方式。
当我们以自下而上的方式移动时，我们会将节点与其父节点进行比较。
这称为Up Heapify。
大堆代码是：
private void heapifyUp(int pos) {
int temp = Heap[pos];
while(pos>0 && temp > Heap[parent(pos)]){
Heap[pos] = Heap[parent(pos)];
pos = parent(pos);
}
Heap[pos] = temp;
}
我们使用while循环而不是递归编写了up heapify的代码。
4.插入新节点
将新元素添加到数组的末尾，并执行交换以确保堆属性成立。
插入算法为：
- 增加堆大小
- 将新元素保留在堆的末尾(数组)
- 从下到上堆砌
插入的代码是：
public void insert(int element) {
Heap[++size] = element;
int current = size;
heapifyUp(current);
}
5.删除/提取节点
要从堆中删除/提取节点，我们从根中删除元素。
根始终提供最大元素。
删除算法如下：
将第一个元素复制到变量中。
将最后一个元素复制到第一个位置(根)。
调用downHeapify()。
删除的代码是：
public int extractMax() {
int max = Heap[1];
Heap[1] = Heap[size--];
downHeapify(1);
return max;
}
其中我们使用size–减小堆的大小。
Java中Max Heap的完整实现
Max Heap的完整java实现如下。
package com.theitroad;
public class Main {
static class MaxHeap {
private int[] Heap;
private int size;
private int maxsize;
public MaxHeap(int size) {
this.maxsize = size;
this.size = 0;
Heap = new int[this.maxsize + 1];
Heap[0] = Integer.MAX_VALUE;
}
private int parent(int pos) {
return pos/2;
}
private int leftChild(int pos) {
return (2 * pos) ;
}
private int rightChild(int pos) {
return (2 * pos) + 1;
}
private void swap(int fpos, int spos) {
int tmp;
tmp = Heap[fpos];
Heap[fpos] = Heap[spos];
Heap[spos] = tmp;
}
private void downHeapify(int pos) {
if (pos >= (size/2) && pos <= size)
return;
if (Heap[pos] < Heap[leftChild(pos)] ||
Heap[pos] < Heap[rightChild(pos)]) {
if (Heap[leftChild(pos)] > Heap[rightChild(pos)]) {
swap(pos, leftChild(pos));
downHeapify(leftChild(pos));
} else {
swap(pos, rightChild(pos));
downHeapify(rightChild(pos));
}
}
}
private void heapifyUp(int pos) {
int temp = Heap[pos];
while(pos>0 && temp > Heap[parent(pos)]){
Heap[pos] = Heap[parent(pos)];
pos = parent(pos);
}
Heap[pos] = temp;
}
public void insert(int element) {
Heap[++size] = element;
int current = size;
heapifyUp(current);
}
public void print() {
for (int i = 1; i <= size/2; i++) {
System.out.print(+ Heap[i] + ": L- " +
Heap[2 * i] + " R- " + Heap[2 * i + 1]);
System.out.println();
}
}
public int extractMax() {
int max = Heap[1];
Heap[1] = Heap[size--];
downHeapify(1);
return max;
}
}
public static void main(String[] arg)
{
MaxHeap maxHeap = new MaxHeap(15);
maxHeap.insert(1);
maxHeap.insert(4);
maxHeap.insert(2);
maxHeap.insert(5);
maxHeap.insert(13);
maxHeap.insert(6);
maxHeap.insert(17);
maxHeap.print();
System.out.println("The max is " + maxHeap.extractMax());
}
}
Output : 17: L- 5 R- 13 5: L- 1 R- 4 13: L- 2 R- 6 The max is 17
