Java 实现堆及其功能，mybatis 的原理实现过程

this.elem[child]=this.elem[parents];

this.elem[parents]=tmp;

parents=child; //判断下面的树也要调整为大堆，

child=2*parents+1;

}else {

break;//结束循环

}

}

}

二、入堆（入队列）

============================================================================

先尾插法方式放入数组，将元素放到最后一个位置，向上调整，不需要比较左右孩子大小，只比较和父亲结点大小即可，

public void adjustUp(int child){

int parents=(child-1)/2;

while(child>0){

if(this.elem[child]>this.elem[parents]){

//交换

int tmp=this.elem[child];

this.elem[child]=this.elem[parents];

this.elem[parents]=tmp;

child=parents;

parents=(child-1)/2;

}else {

break;

}

}

}

三、出堆（出队列）

============================================================================

返回优先级最高的对象，即头节点，将头结点和最后一个元素交换，剪掉最后一个元素，调用调整方法重新键堆

代码如下（示例）：

public void pop(){

/* if(isEmpty()){

return;

}*/

int tmp=this.elem[0];

this.elem[0]=this.elem[this.usedSize-1];

this.elem[this.usedSize-1]=tmp;

this.usedSize--;

adjust

《Android学习笔记总结+最新移动架构视频+大厂安卓面试真题+项目实战源码讲义》
浏览器打开：qq.cn.hn/FTe 免费领取

Down(0,this.usedSize);

}

四、优先级队列

==========================================================================

PriorityQueue<Integer>priorityQueue=new PriorityQueue<>();//优先级队列 默认是小堆

//改为大堆

PriorityQueue<Integer>priorityQueue1=new PriorityQueue<>(new Comparator<Integer>() {//改为大堆

@Override

public int compare(Integer o1, Integer o2) {

return o2-o1;

}

});

五、TopK 问题

===========================================================================

即找出数组中前 K 个最值问题，时间复杂度为 nlogK,

如果找的是前 K 个最大值，

1.建立大小为 K 的小堆

2.遍历数组将 K 个元素放入堆中

3.从 K+1 位置开始和堆顶元素进行比较

4.如果比堆顶元素大的话，就出小的元素，之后大的入堆

5.最终输出小堆就前 K 个最大元素

找最小值就是建大堆。

public static void TopK(int[]array,int k){

PriorityQueue<Integer> minHeap=new PriorityQueue<>(k);

for (int i=0;i<array.length;i++){

if(k>0){

minHeap.offer(array[i]);

k--;

}else {

Integer val=minHeap.peek();

if(array[i]>val){//如果 K+1 位置的值大于堆顶的元素 就出

minHeap.poll();

minHeap.offer(array[i]);

}

}

}

System.out.println(minHeap);

}

六、堆排序

========================================================================

从小到大排序，建立一个大堆 每次将堆顶元素和最后位置元素调换，end 位置减 1，将所有位置都调整完成后，就是有序的。

//堆排序 从小到大排序 应该是建大堆（能知道最上面是最大的）

public static void heapSort(int []array){

createHeap(array);

int end=array.length-1;

// while(){//循环 建立大堆 每次都是头最大 交换 尾巴节点

while (end>0){

int tmp=array[0];

array[0]=array[end];

array[end]=tmp;

adjust(array,0,end);

end--;

}

}

public static void adjust(int []array,int parent,int len){

int child=2*parent+1;

while(child<len){

if(child+1<len&&array[child+1]>array[child]){

child++;

}

if(array[child]>array[parent]){

int tmp=array[parent];

array[parent]=array[child];

array[child]=tmp;

parent=child;

child=2*parent+1;

}else {

break;

}