一、堆的定义
在计算机科学中，堆（heap）是一种特殊的树状数据结构。用于存储和管理数据。堆通常用于实现优先队列。其中具有最高（或最低）优先级的元素始终位于堆的根部。
堆分为最小堆和最大堆两种类型：
- 最小堆：父节点的值小于或等于其子节点的值。
- 最大堆：父节点的值大于或等于其子节点的值。
二、堆的特性
1、堆是一个完全二叉树，通过数组的方式来存储的完全二叉树。将这个树层序遍历，遍历的结果依次添加到数组中，遇到 空节点 则将 空节点 也添加到数组中
放进 null 是为了维护父子之间的下标关系，可以通过下标换算出父子关系
设 父节点下标为 parent ，左子树的下标就是 2*parent+1 ,右子树的下标就是 2*parent+2
设 子节点下标为 child 父节点的下标（child - 1） / 2
（普通的二叉树可能包含大量的 null 导致内存利用率低所以不使用数组表示）
2、对于堆来说，任何一个节点，值都小于（或大于）两个子节点的值，两个子节点的值谁大谁小没关系。树的树根节点（ 数组下标为[0] ）的元素，就是整个树的 最小值/最大值。
三、堆的实现
1、向下调整/下沉式调整
有一个数组，除了 [0] 元素之外，其他的元素都满足小堆的要求
针对上述情况，就需要用到 向下调整
第一步：先确定要比较的节点是哪一个，如果只有左子树，就直接和左子树比，如果同时有左右子树，先比较左右子树中更小的那一个
第二步：拿着更小的节点和根节点进行比较，如果根节点比子节点大，交换两个节点的值。
2.构建堆的基本思路
从最后一个非叶子节点出发，从后往前遍历，针对每个节点进行向下调整
package PriorityQueue;
import java.util.Arrays;
public class Heap {
/**
*向下调整
* @param array 要调整的堆
* @param size 堆的大小
* @param index 从哪个位置开始向下调整
*/
public static void shiftDown(int[] array,int size,int index){
//要调整的父节点
int parent = index;
//计算要调整的左子树节点
int child = 2 * parent + 1;
//如果子节点下标超出数组范围，说明子节点不存在
//主循环就结束，调整就完成了
while (child < size){
//左子树+1得到右子树,通过这个判断找出左右子树更小的值
if(child + 1 < size && array[child + 1] < array[child]){
child = child + 1;
}
//然后比较 child 和 parent 的大小关系
if(array[parent] <= array[child]){
break;
//父节点比子节点小，已经符合小堆规则，不需要再调整了
} else {
//交换父子的值
int tmp = array[parent];
array[parent] = array[child];
array[child] = tmp;
//更新 parent 和 child 的指向
parent = child;
child = 2 * parent + 1;
}
}
}
/**
* 建堆操作
* @param array
*/
public static void creatHeap(int[] array){
//1.找到最后一个非叶子节点
//2.从后往前循环进行向下调整
int lastLeaf = array.length - 1;
int lastParent = (lastLeaf - 1) / 2;
for(int i = lastParent;i>=0;i--){
shiftDown(array,array.length,i);
}
}
/**
* 向上调整堆，整个数组只有最后一个元素不满足堆的要求
* 在这个前提下，堆最后一个元素进行向上调整
* @param array
* @param index
*/
public static void shiftUp(int[] array,int index){
int child = index;
int parent = (child - 1) / 2;
//child为0，说明已经到根节点了，循环就结束了
while (child > 0){
if(array[parent] > array[child]){
//此时应该要进行交换
int tmp = array[parent];
array[parent] = array[child];
array[child] = tmp;
//更新 child 和 parent 的指向
child = parent;
parent = (child - 1) / 2;
}else {
//此时符合堆，不需要再调整了
break;
}
}
}
public static void main(String[] args) {
int[] array = {1,3,2,6,5,7,8,9,10,0};
creatHeap(array);
System.out.println(Arrays.toString(array));
}
}
可以看到最后的结果已经满足堆的要求了，整体的建堆时间复杂度是 O（N）
四、优先级队列
队列的核心操作：
1.入队列
新添加的元素可能会打破原有的堆的规则，针对新来的元素就需要进行 “向上调整”
/**
* 向上调整堆，整个数组只有最后一个元素不满足堆的要求
* 在这个前提下，堆最后一个元素进行向上调整
* @param array
* @param index
*/
private static void shiftUp(int[] array,int index){
int child = index;
int parent = (child - 1) / 2;
//child为0，说明已经到根节点了，循环就结束了
while (child > 0){
if(array[parent] > array[child]){
//此时应该要进行交换
int tmp = array[parent];
array[parent] = array[child];
array[child] = tmp;
//更新 child 和 parent 的指向
child = parent;
parent = (child - 1) / 2;
}else {
//此时符合堆，不需要再调整了
break;
}
}
}
public class MyPriorityQueue {
private int[] arrar;
public int size = 0;
public MyPriorityQueue(){
arrar = new int[1000];
}
//入队列
public void offer(int value){
if(size == arrar.length){
//这里还可以实现一个扩容功能
}
//先把新元素进行尾插
arrar[size] = value;
size++;
//从最后的元素开始向上进行调整
Heap.shiftUp(arrar,size - 1);
}
}2.出队列
队首就是 [0] 元素，需要把这个元素删除掉，但是在堆中，直接删掉根节点，后续的节点往期走就有可能导致堆的规则发生改变。而最后一个节点删除不会造成其他影响，所以可以通过先交换首尾的值，再对尾元素删除，最后对首进行向下调整。
//出队列
public Integer poll(){
if(size == 0){
return null;
}
//先把第一个元素和最后一个元素交换
int ret = arrar[0];
arrar[0] = arrar[size - 1];
//这一步写不写无所谓，因为size--就把这个元素删了
arrar[size - 1] = ret;
size--;
Heap.shiftDown(arrar,size,0);
return ret;
}3.取队首元素
public Integer peek(){
if(size == 0){
return null;
}
return arrar[0];
}测试
public class text2 {
public static void main(String[] args) {
MyPriorityQueue queue = new MyPriorityQueue();
queue.offer(3);
queue.offer(4);
queue.offer(2);
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
}
}
4.给优先级队列指定比较规则
Java标准库中有这样两个接口：Comparable 和 Comparator 就是用来描述比较规则的
Comparable : 如果队列插入的是类的对象，就可以让这个类实现 Comparable 接口
（内部制定规则，比较自己和别人）
Comparator : 如果队列插入的是 int 或 String 这种，此时就可以实现 Comparator 来完成上述规则
（第三方，比较两个内容）
写法一：
//泛型参数取决于你要比较什么
class IntComparator implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
//此处是自定义比较规则，原来的规则就不要了
//如果判断 o1 比 o2 小，就返回一个 < 0 的整数
//如果判断 o1 比 o2 大，就返回一个 > 0 的整数.
//如果判断 o1 比 o2 相等，就返回 0
//这里就是定义了大堆的比较规则，o1 - o2就是小堆
return o2 - o1;
}
}写法二：
//这个写法是“匿名内部类”写法，实现了 Comparator 接口，重写了 Comparator 的 compare 方法，同时创建了内部类的实例
//只能创建一次！！
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});使用优先级队列保存自定义的类型
package PriorityQueue;
import java.util.PriorityQueue;
class Student implements Comparable<Student>{
public int id;
public String name;
public int score;
public Student(int id,String name,int score){
this.id = id;
this.name = name;
this.score = score;
}
@Override
public String toString() {
return "Student{" +
"id=" + id +
", =name='" + name + '\'' +
", score=" + score +
'}' + '\n';
}
//对于 Comparator 来说，是有两个参数，比较 o1 和 o2 的关系
//对应 Comparable 来说，看起来是一个参数，实际上是拿 this 和 o 进行比较
//使用 Comparable 的前提就是这个类是你自己写的
@Override
public int compareTo(Student o) {
//大堆的写法，比较分数
return o.score - this.score;
}
}
public class text3 {
public static void main(String[] args) {
PriorityQueue<Student> queue = new PriorityQueue<>();
queue.offer(new Student(1,"Alice",88));
queue.offer(new Student(2,"Bob",90));
queue.offer(new Student(3,"Charlie",70));
queue.offer(new Student(4,"David",85));
System.out.println(queue.toString());
}
}
还可以同时写多种 Comparator 种比较方法
class StudentComparator1 implements Comparator<Student>{
@Override
public int compare(Student o1,Student o2){
return o2.score - o1.score;
}
}
class StudentComparator2 implements Comparator<Student>{
@Override
public int compare(Student o1,Student o2){
return o2.id - o1.id;
}
}
class StudentComparator3 implements Comparator<Student>{
@Override
public int compare(Student o1,Student o2){
return o1.name.compareTo(o2.name);
}
}
