堆是一种类似于二叉树的数据结构，不过底层实现是数组，将数组元素组织成一棵二叉树的样子，通过索引操作元素；
在讲解堆之前先讲解一个概念，那就是完全二叉树，完全二叉树是指每一层都铺满之后再去下一层从左往右排列元素；
本节我们讲解堆中的最大堆，就是一种完全二叉树的结构；底层实现借助的是我们数据结构篇01讲解的动态数组；
1、最大堆构造函数与基本函数
这里提供了三种构造函数，第一种指定最大堆容量；第二种默认容量为10；第三种接受一个数组，并将数组转化为堆，其中里面使用的parent函数和siftDown我们后面会详细讲解；
size函数表示最大堆中的元素个数；
isEmpty函数表示最大堆是否为空；
public class MaxHeap<E extends Comparable<E>> {
private Array<E> data;
public MaxHeap(int capacity){
data = new Array<>(capacity);
}
public MaxHeap(){
data = new Array<>();
}
public MaxHeap(E[] arr){
data = new Array<>(arr);
if(arr.length != 1){
for(int i = parent(arr.length - 1) ; i >= 0 ; i --)
siftDown(i);
}
}
// 返回堆中的元素个数
public int size(){
return data.getSize();
}
// 返回一个布尔值, 表示堆中是否为空
public boolean isEmpty(){
return data.isEmpty();
}
、、、
}
复制代码2、求堆中元素父节点及左右孩子节点的索引
因为最大堆是一棵完全二叉树的结构，因此每一层从左往右排列，排满了再去下层继续从左往右排，我们是从索引0开始排列的；
我们画出这样一个完全二叉树的结构之后，就会很容易发现每个节点的父亲节点的索引以及每个节点的左右两个孩子节点的索引；
// 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
private int parent(int index){
if(index == 0)
throw new IllegalArgumentException("index-0 doesn't have parent.");
return (index - 1) / 2;
}
// 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
private int leftChild(int index){
return index * 2 + 1;
}
// 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
private int rightChild(int index){
return index * 2 + 2;
}
复制代码3、向堆中添加元素
首先将元素添加到动态数组的尾部，然后对数组的最后一个元素执行siftUp操作，最后一个元素也就是我们刚刚添加的那个元素；
siftUp元素上浮是这样一个过程，如果当前元素的值比它的父节点的元素值还大，那么就将当前元素的值和父节点的值交换位置，循环执行这个过程，直到走完根节点；
注意我们这里实现的是最大堆，如果是实现最小堆，那么需要将元素值小的节点上浮；
// 向堆中添加元素
public void add(E e){
data.addLast(e);
siftUp(data.getSize() - 1);
}
//元素上浮
private void siftUp(int k){
while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0 ){
data.swap(k, parent(k));
k = parent(k);
}
}
复制代码4、取出堆中最大元素
因为我们实现的是一个最大堆，因此取出堆中的最大元素也就是取出根节点的元素，但我们取出根节点之后还要维护最大堆的性质；
findMax查看堆中的最大元素，就是返回索引为0的根节点的值；
extractMax取出堆中最大元素，首先将根节点和数组最后一个位置的元素互换位置，然后将数组的最后一个元素删除，最后将根节点执行siftDown元素下沉操作。为什么要进行这个siftDown呢？因为现在的根节点是从数组尾换过来的，所以肯定不是堆中的最大元素，所以执行siftDown去下沉根节点；
siftDown元素下沉是这样一个过程，首先找出当前节点的左右两个孩子节点中的最大值，然后将最大值与当前节点比较，如果当前节点比最大值还大的话，说明满足最大堆的性质，直接break跳出循环；如果当前节点比最大值下的话，将当前节点与最大值节点交换位置，然后将当前节点替换为最大值节点继续往下一层比较，直到走完叶子节点；
// 看堆中的最大元素
public E findMax(){
if(data.getSize() == 0)
throw new IllegalArgumentException("Can not findMax when heap is empty.");
return data.get(0);
}
// 取出堆中最大元素
public E extractMax(){
E ret = findMax();
data.swap(0, data.getSize() - 1);
data.removeLast();
siftDown(0);
return ret;
}
//元素下沉操作
private void siftDown(int k){
while(leftChild(k) < data.getSize()){
int j = leftChild(k); // 在此轮循环中,data[k]和data[j]交换位置
if( j + 1 < data.getSize() &&
data.get(j + 1).compareTo(data.get(j)) > 0 )
j ++;
// data[j] 是 leftChild 和 rightChild 中的最大值
if(data.get(k).compareTo(data.get(j)) >= 0 )
break;
data.swap(k, j);
k = j;
}
}
复制代码5、取出堆中最大元素并替换
replace函数表示这样一个过程，取出堆中的最大元素并返回，然后将参数元素e添加到最大堆中；
直接将根节点替换为元素e，然后对根节点执行元素下沉siftDown操作即可；
// 取出堆中的最大元素，并且替换成元素e
public E replace(E e){
E ret = findMax();
data.set(0, e);
siftDown(0);
return ret;
}
复制代码6、借助最大堆实现优先队列
优先队列如下所示，优先队列也是一个队列，因此可以实现我们在数据结构篇04中的队列接口；
但优先队列不同于一般的队列了，并不遵循先进先出的规则了；而是优先级最高的元素先出队，这个优先级需要我们自己定义了，因此优先队列中的泛型必须继承自Comparable接口；
我们从优先队列的实现中可以看出，其实就是对最大堆接口的一层封装，主要的功能在最大堆中实现了；
enqueue入队列操作直接往最大堆中添加元素即可，在最大堆中会维护最大堆的结构；
dequeue出队操作直接取出堆的最大元素即可，也就是根节点的值，同样取出之后在最大堆中会自己维护最大堆的结构；
public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
private MaxHeap<E> maxHeap;
public PriorityQueue(){
maxHeap = new MaxHeap<>();
}
@Override
public int getSize(){
return maxHeap.size();
}
@Override
public boolean isEmpty(){
return maxHeap.isEmpty();
}
@Override
public E getFront(){
return maxHeap.findMax();
}
@Override
public void enqueue(E e){
maxHeap.add(e);
}
@Override
public E dequeue(){
return maxHeap.extractMax();
}
}
复制代码7、最大堆的完整代码
public class MaxHeap<E extends Comparable<E>> {
private Array<E> data;
public MaxHeap(int capacity){
data = new Array<>(capacity);
}
public MaxHeap(){
data = new Array<>();
}
public MaxHeap(E[] arr){
data = new Array<>(arr);
if(arr.length != 1){
for(int i = parent(arr.length - 1) ; i >= 0 ; i --)
siftDown(i);
}
}
// 返回堆中的元素个数
public int size(){
return data.getSize();
}
// 返回一个布尔值, 表示堆中是否为空
public boolean isEmpty(){
return data.isEmpty();
}
// 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
private int parent(int index){
if(index == 0)
throw new IllegalArgumentException("index-0 doesn't have parent.");
return (index - 1) / 2;
}
// 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
private int leftChild(int index){
return index * 2 + 1;
}
// 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
private int rightChild(int index){
return index * 2 + 2;
}
// 向堆中添加元素
public void add(E e){
data.addLast(e);
siftUp(data.getSize() - 1);
}
private void siftUp(int k){
while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0 ){
data.swap(k, parent(k));
k = parent(k);
}
}
// 看堆中的最大元素
public E findMax(){
if(data.getSize() == 0)
throw new IllegalArgumentException("Can not findMax when heap is empty.");
return data.get(0);
}
// 取出堆中最大元素
public E extractMax(){
E ret = findMax();
data.swap(0, data.getSize() - 1);
data.removeLast();
siftDown(0);
return ret;
}
private void siftDown(int k){
while(leftChild(k) < data.getSize()){
int j = leftChild(k); // 在此轮循环中,data[k]和data[j]交换位置
if( j + 1 < data.getSize() &&
data.get(j + 1).compareTo(data.get(j)) > 0 )
j ++;
// data[j] 是 leftChild 和 rightChild 中的最大值
if(data.get(k).compareTo(data.get(j)) >= 0 )
break;
data.swap(k, j);
k = j;
}
}
// 取出堆中的最大元素，并且替换成元素e
public E replace(E e){
E ret = findMax();
data.set(0, e);
siftDown(0);
return ret;
}
}
复制代码
![[02/27][官改] Simplicity@MIX2 ROM更新-一一网](https://www.proyy.com/wp-content/uploads/2020/02/3168457341.jpg)
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
