堆是什么
1.是一种特殊的二叉树（完全二叉树） 2.通过数组的方式顺序存储 3.对于这个数的任意节点来说，满足根节点大于左右子树的值（大堆），或者任意一节点满足根节点的值小于左右子树的值（小堆）
堆能干啥
1.能高效得找出一个集合的最大/最小元素（堆顶元素） 2.能高效得找到前K大/前K小的元素（topk问题）
核心操作
向下调整 & 向上调整
1.向下调整（以大根堆为例）
时间复杂度：O(logN) (size固定，child每次乘以2)
代码语言：javascript复制 //按照大堆来实现
//向下调整
//size ☞ array中那部分内容为堆
//index ☞ 从哪个位置开始向下调整
//如果父节点的下标为i，左子树的下标为2*i 1，右子树的下标为2*i 2
//子节点的下标为i，父节点的下标为（i-1）/2
public static void shiftDown(int[] array, int size, int index){
int parent = index;
int child = parent * 2 1;
while (child < size){
//里面的条件的含义，是看看parent有没有子节点
//把左右子树中较大的节点
if (child 1 < size && array[child 1] > array[child]){
child = child 1;
}
//上述完成后，child一定是最大的元素
if (array[child] > array[parent]){
//需要交换
int tmp = array[child];
array[child] = array[parent];
array[parent] = tmp;
}else {
//说明当前位置开始已经符合堆的要求了
break;
}
parent = child;
child = 2*parent 1;
}
}
public static void createHeap(int[] array, int size){
//基于向下调整
//建堆可以基于向下调整和向上调整
//如果是向下调整，就需要从后往前遍历数组
for (int i = (size - 1 - 1)/2; i>= 1; i--){
shiftDown(array,size,i);
}
}
public static void main(String[] args) {
int[] array = {9,5,2,7,3,6,8};
createHeap(array,array.length);
System.out.println(Arrays.toString(array));
}2.向上调整
代码语言：javascript复制 //向上调整
//此时size这个参数其实不需要用到，判断是否调整完了只需要和0比较就行了
private int[] array = new int[100];
private int size = 0;
public static void shiftUp(int[] array, int size, int index){
int child = index;
int parent = (child - 1)/2;
while (child > 0){
if (array[parent] < array[child]){
//当前不符合大堆要求
int tmp = array[parent];
array[parent] = array[child];
array[child] = tmp;
}else {
break;
}
child = parent;
parent = (child - 1) / 2;
}
}添加/删除/取堆顶元素
1）添加元素（使用向上调整）
代码语言：javascript复制 private int[] array = new int[100];
private int size = 0;
public void offer(int x){
//新加的元素放到了数组的最后，把这个新加的节点就弄成child
array[size] = x;
size ;
//把新加入的元素进行向上调整
shiftUp(array,size - 1);
}
public static void shiftUp(int[] array, int index){
int child = index;
int parent = (child - 1)/2;
while (child > 0){
if (array[parent] < array[child]){
//当前不符合大堆要求
int tmp = array[parent];
array[parent] = array[child];
array[child] = tmp;
}else {
break;
}
child = parent;
parent = (child - 1) / 2;
}
}2）删除元素（使用向下调整）
代码语言：javascript复制 public int poll(){
//下标为0的元素就是队首元素，删掉的同时，剩下的队列也是堆
//要删除堆顶元素，直接把数组中的最后一个元素给赋值到堆顶元素
//同时 size-- 就把元素删掉了
int oldValue = array[0];
array[0] = array[size-1];
size--;
shiftDown(array,size,0);
return oldValue;
}
public static void shiftDown(int[] array, int size, int index){
int parent = index;
int child = parent * 2 1;
while (child < size){
//里面的条件的含义，是看看parent有没有子节点
//把左右子树中较大的节点
if (child 1 < size && array[child 1] > array[child]){
child = child 1;
}
//上述完成后，child一定是最大的元素
if (array[child] > array[parent]){
//需要交换
int tmp = array[child];
array[child] = array[parent];
array[parent] = tmp;
}else {
//说明当前位置开始已经符合堆的要求了
break;
}
parent = child;
child = 2*parent 1;
}
}3）取堆顶元素
代码语言：javascript复制 public int peek(){
return array[0];
}标准库中的优先队列
代码语言：javascript复制import java.util.PriorityQueue;
public class TestPriorityQueue {
//标准库的优先队列(默认为小堆)
public static void main(String[] args) {
PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.offer(9);
queue.offer(5);
queue.offer(2);
queue.offer(7);
queue.offer(3);
queue.offer(6);
while (!queue.isEmpty()){
int cur = queue.poll();
System.out.println(cur);
}
}
}
