堆概念的介绍
在之前的文章中介绍过，队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列。
在优先级队列PriorityQueue中，底层使用的是堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整。每一个父亲节点都比子节点小称为小根堆，每一个父亲节点都比子节点大称为大根堆，如下图所示
堆的存储方式
在堆的概念中提到，堆是一个完全二叉树，在存储的过程中一般采用顺序存储的方式进行，例如有一个集合为{27,15,19,18,28,34,65,49,25,37}，则在其堆中的存储的逻辑结构为
如上所示，在逻辑上为一个完全二叉树，如要将其调整为小根堆或大根堆（以大根堆为例），可以采用将根节点向上调整的方式
堆的创建
向上过程（以大堆为例）
1.让指针parent标记要调整的节点，指针child标记孩子节点中，大孩子的节点
2.将parent与child进行比较，如果child比parent大，则进行交换
循环如上的过程，完成后则调整为大根堆
代码如下
public class MyBigQueue {
public int[] elem; //采用数组的方式调整
public int usesize; //标志有效数字
public MyBigQueue() {
this.elem = new int[10]; //初试化数组大小为10，后期不够再扩容
}
public void initElem(int[] array){ //传一个数组初试化elem,并将elem调整为大根堆
for (int i = 0; i < array.length; i++) {
elem[i]=array[i];
usesize++;
}
}
public void CreatBigQ(){
for(int parent=(usesize-1-1)/2;parent>=0;parent--){ //自下而上，确定父亲节点
shifDown(parent,usesize); //将每个父亲节点放入方法中进行至下而上的调整
}
}
public void shifDown(int parent,int end){ //写调整的方法
int child = parent*2+1;
while (child<end){ //孩子节点只要没走到数组的结尾就继续遍历
if(child+1<usesize&&elem[child]<elem[child+1]){
child++; //走完这一步，child走到了孩子节点的最大值下
}
if(elem[child]>elem[parent]){ //判断是否需要交换
swap(child,parent); //交换另写一个方法
parent=child; //交换完后，
child=child*2+1; //孩子节点走向孩子节点的左孩子节点
}else {
break;
}
}
}
public void swap(int x,int y){
int tmp = elem[x];
elem[x]=elem[y];
elem[y]=tmp;
}在二叉树中，一个节点如果有左孩子节点，则左孩子节点的下标为2*X+1(X为当前节点下标)，所以有上述代码 child=child*2+1;
验证
在传入数组arr后，elem为按顺序方式存储的大根堆
堆的删除
注意：堆的删除一点删除的是堆顶的元素
删除理论如下：
1.将堆顶元素对堆中最后一个元素交换
2.将堆的有效数据减少一个，也就是usesize-1；
3.将堆顶元素进行向下调整
代码如下
public int poll(){
int tmp = elem[0]; //保存要删除的头节点
swap(0,usesize-1); //将头节点和尾节点交换
usesize--; //将有效位数减一位
shifDown(0,usesize); //传入头节点，向下调整
return tmp;
}验证
头节点置为末尾，有效位数减1，则再遍历时，遍历不到65，视为删除
堆的插入
插入理论如下：
1. 先将元素放入到底层空间中(注意：空间不够时需要扩容)
2.将最后新插入的节点向上调整，直到满足堆的性质
注意，在之前写的代码中，shifDown是向下调整的方法，向上调整需要要重写
代码如下
public boolean isFull(){
return usesize==elem.length; //当有效位和数组的长度相同时，代表数组满了
}
public void offer(int val){
if(isFull()){ //判断数组是否满了，如果满了就进行扩容
this.elem= Arrays.copyOf(elem,elem.length*2);
}
elem[usesize]=val; //将新插入的数据置为数组最后
usesize++; //有效位加1
shifUp(usesize-1); //进行向上调整，传入插入数据的下标，视为孩子节点
}
public void shifUp(int child){
int parent = (child-1)/2; //根据孩子节点确定父亲节点
while (child>0){ //孩子节点还大于头节点的时候，就继续遍历
if(elem[child]>elem[parent]){ //孩子节点的值大于父亲节点的值，就进行交换
swap(child,parent);
child=parent; //将父亲节点给孩子，进行向上调整
parent=(child-1)/2; //父亲节点给自己的父亲节点
}else {
break;
}
}
}测试如下
全部的完整代码如下
import java.util.Arrays;
public class MyBigQueue {
public int[] elem; //采用数组的方式调整
public int usesize; //标志有效数字
public MyBigQueue() {
this.elem = new int[10]; //初试化数组大小为10，后期不够再扩容
}
public void initElem(int[] array){ //传一个数组初试化elem,并将elem调整为大根堆
for (int i = 0; i < array.length; i++) {
elem[i]=array[i];
usesize++;
}
}
public void CreatBigQ(){
for(int parent=(usesize-1-1)/2;parent>=0;parent--){ //自下而上，确定父亲节点
shifDown(parent,usesize); //将每个父亲节点放入方法中进行至下而上的调整
}
}
public void shifDown(int parent,int end){ //写调整的方法
int child = parent*2+1;
while (child<end){ //孩子节点只要没走到数组的结尾就继续遍历
if(child+1<usesize&&elem[child]<elem[child+1]){
child++; //走完这一步，child走到了孩子节点的最大值下
}
if(elem[child]>elem[parent]){ //判断是否需要交换
swap(child,parent); //交换另写一个方法
parent=child; //交换完后，
child=child*2+1; //孩子节点走向孩子节点的左孩子节点
}else {
break;
}
}
}
public void swap(int x,int y){
int tmp = elem[x];
elem[x]=elem[y];
elem[y]=tmp;
}
public int poll(){
int tmp = elem[0];
swap(0,usesize-1);
usesize--;
shifDown(0,usesize);
return tmp;
}
public boolean isFull(){
return usesize==elem.length; //当有效位和数组的长度相同时，代表数组满了
}
public void offer(int val){
if(isFull()){ //判断数组是否满了，如果满了就进行扩容
this.elem= Arrays.copyOf(elem,elem.length*2);
}
elem[usesize]=val; //将新插入的数据置为数组最后
usesize++; //有效位加1
shifUp(usesize-1); //进行向上调整，传入插入数据的下标，视为孩子节点
}
public void shifUp(int child){
int parent = (child-1)/2; //根据孩子节点确定父亲节点
while (child>0){ //孩子节点还大于头节点的时候，就继续遍历
if(elem[child]>elem[parent]){ //孩子节点的值大于父亲节点的值，就进行交换
swap(child,parent);
child=parent; //将父亲节点给孩子，进行向上调整
parent=(child-1)/2; //父亲节点给自己的父亲节点
}else {
break;
}
}
}
public void getElem(){
for (int i = 0; i < elem.length; i++) {
System.out.println(elem[i]);
}
}
}
测试代码
public class Main {
public static void main(String[] args) {
MyBigQueue myBigQueue = new MyBigQueue();
int[] arr = {27,15,19,18,28,34,65,49,25,37};
myBigQueue.initElem(arr);
myBigQueue.CreatBigQ();
System.out.println("=========");
myBigQueue.poll();
System.out.println("=========");
myBigQueue.offer(99);
myBigQueue.offer(78);
myBigQueue.offer(108);
System.out.println("=========");
myBigQueue.getElem();
}
}