一、堆的概念
1、堆在逻辑上是一颗完全二叉树（类似于一颗满二叉树只缺了右下角）
2、堆的实现利用的是数组，我们通常会利用动态数组来存放元素，这样可以快速拓容也不会很浪费空间，我们是将这颗完全二叉树用层序遍历的方式储存在数组里的
3、堆有两种分别是大根堆和小根堆
二、大根堆
大根堆就是整个完全二叉树，任意一个根节点的值都比左右子树的值大。
这就是一个大根堆，所有根节点的值永远比左右子树的大，那么就可以看出，整棵树的根节点，他的值是整个堆中最大的。同时我们也发现没有直接父子关系的节点他们的值没有完全地关系，就像第二层的33和第三层的45以及20，没有规定第三层的元素值必须小于第二层，只要满足根节点比自己左右子树节点的值大即可。
三、小根堆
小根堆表示整个完全二叉树，任意一个根节点的值都比左右子树的值小。
以上就是一个简单地小根堆它的定义与大根堆相似，只是跟节点的值小于自己的左右节点的值，同时小根堆的层与层之间没有直接关系的节点的值也没有必然的大小关系。
四、将随机数组变成堆
我们用一个完全二叉树来模拟堆，同时用数组的方式存储整个队的元素值，需要我们将一个乱序的数组变成一个大根堆或者小根堆。
对于堆化我们选择循环遍历原数组，不断地向堆尾进行添加操作，当添加了一个新的元素之后利用上浮操作堆化。若新添加的元素大于自己的父节点，那么就进行上浮； 若没有小于等于父节点则表示当前的堆满足条件，不需要再进行变动。
我们这里实现将一个数组变成最大堆的过程，假设乱序数组是[2, 6, 3, 4, 1]，最终经过堆化变成了最大堆[6, 4, 3, 2, 1]。
通过图片我们大概了解了具体过程，先将元素插入到堆的最后，再与当前的父节点的值进行比较，若大，则进行上浮操作，与父节点进行交换，不断地与父节点进行比较，直到不大于父节点或者已经是整颗二叉树的根节点的时候表示一个元素已经添加完毕，并且当前的堆是一个最大堆，直到原数组所有的元素都添加完毕后表示已经将整个数组变成了一个大根堆。
下面我们用代码来实现一下主要步骤：
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
public class MaxHeap {
private List data;
//构造函数
public MaxHeap(int count){
//我们通过动态数组来实现
this.data = new ArrayList<>(count);
}
public MaxHeap(){
this(10);
}
//根据下标找到父节点的下标
private int parent(int i){
return (i-1) >> 1;
}
//根据下标找到当前节点的左子树下标
private int leftChild(int i){
return (i << 1) + 1;
}
//根据下标找到当前节点的右子树下标
private int rightChild(int i){
return (i << 1) + 2;
}
public void add(int val){
this.data.add(val);
siftUp(data.size()-1);
}
//上浮
private void siftUp(int i) {
//当该元素到最顶端或它的值不大于当前根节点的值的时候表示上浮完成
while (i > 0 && data.get(i) > data.get(parent(i)))
{
//保存房钱父节点的下标
int parent = parent(i);
//进行交换
swap(i,parent);
//再将要进行判断的下标更新后继续循环判断
i = parent;
}
}
//交换操作
private void swap(int i, int parent) {
int temp = data.get(i);
data.set(i, data.get(parent));
data.set(parent,temp);
}
//取出当前最大堆的最大元素并返回最大的元素
//同时将推重新排列
public int extractMax(){
if(data.size() == 0)
{
throw new NoSuchElementException("this heap is null!");
}
//最大堆的堆顶是最大的
int max = data.get(0);
//堆的最后一个元素
int last = data.get(data.size() - 1);
//把最后一个元素放到堆顶
data.set(0, last);
//最后一个元素放上去之后把最后的这个删掉
data.remove(data.size() - 1);
//从堆顶开始下沉，重新将堆变成堆
siftDown(0);
return max;
}
//覆写toString方法
@Override
public String toString() {
return data.toString();
}
public static void main(String[] args) {
int[] data = {17,90,68,12,15,14,70,30,20};
MaxHeap heap = new MaxHeap(data.length);
for (int i = 0 ; i< data.length ; i++)
{
heap.add(data[i]);
}
System.out.println(heap);
}
}
结果：
