Java数据结构之堆

堆的概念

堆逻辑上是一棵完全二叉树
堆物理上是保存在数组中
满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆
反之，则是小堆，或者小根堆，或者最小堆
堆的基本作用是快速找集合中的最值

二叉树的顺序存储

使用数组保存二叉树结构，方式即将二叉树用层序遍历方式放入数组中。
一般只适合表示完全二叉树，因为非完全二叉树会有空间的浪费。
这种方式的用法就是堆的表示。

顺序存储中的双亲与孩子的下标关系

已知双亲的下标：

左孩子下标 = 2*parent+1;
右孩子下标 = 2*parent+1;

已知孩子下标：

双亲下标 = (child - 1) / 2;

建堆与向上调整
在这里插入图片描述

将二叉树调整成大根堆

public class Heap {// 定义数组和数组的长度public int[] elem;public int usedSize;public Heap(){this.elem = new int[10];}/*** 将一棵树调整大堆的思路*  1.每棵子树都应该变成大堆*  2.最主要的逻辑：从最后一棵子树开始进行调整（从4下标开始）*  3.怎么调整*  4.定义子树父亲节点p 孩子节点c*  5.在父亲节点的左右两边找到左右孩子的最大值*  6.让左右孩子的c 最大值 跟父亲节点进行交换*  7.注意：让p走到c 让c继续走 发现c超出下标 那就证明这棵子树交换完了*  8.然后再调整上一个子树 【其实是换下标 换p换c 继续调整】 树的思想 下标的操作** */public void createHeap(int[] array){for (int i = 0; i < array.length; i++) {// 把数组的值拷贝给 elemthis.elem[i] = array[i];this.usedSize++;}// parent 就代表每棵子树的根节点// 如何拿到最后 最后一个节点的下标: array.length-1// 最后一个节点的父节点: (array.length-1-1)/2for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {// 注意：第2个参数 每次调整的结束位置应该是：不超过数组的最大值，下标不取等于就行// this.usedSizeadjustDown(parent,this.usedSize);}}// root:每棵树的根值 len:数组长度private void adjustDown(int root, int len) {int parent = root;int child = 2*parent+1;// 在调整的过程中 child要小于len 防止数组越界// 只要能进循环 就代表至少有左孩子while (child < len){// 找到左右孩子的最大值// 1.前提是你得有右孩子// 先判断是否有有孩子，并且判断左右孩子哪个大，并保证child是两个孩子中值最大的那一个if(child+1 < len && this.elem[child] < this.elem[child+1]){// 保证child是两个孩子中值最大的那一个child++;}// 保证，child下标的数据 一定是左右孩子的最大值的下标if(this.elem[child] > this.elem[parent]){int tmp = this.elem[child];this.elem[child] = this.elem[parent];this.elem[parent] = tmp;// 先移动parentparent = child;// 再移动childchild = 2*parent+1;}else {// 当调整的过程中，孩子节点没有父亲节点的值大，那么此时说明这棵树已经是大根堆了break;}}}
}

时间复杂度
要计算最坏的时间复杂度，实际上就是一棵满二叉树，这样每棵树都会进行调整

每一层有多少个节点
时间复杂度与节点的高度h和每层节点的个数有关

T(n) = 2^0 * (h-1)+2^1 *(h-2)+…+2^(h-2) * 1

2*T(n) = 2^1 *(h-1)+ 2^2 * (h-2)+2^3 *(h-3)+…+2^(h-1) * 1

错位相减
T(n) = 2^h - 1 - h

假设共有n个节点 n = 2^h - 1
2^h = n+1 h = log2(n+1)

T(n) = n - log2(n+1)
当n慢慢变大的时候，整个表达式的结果就趋近于n

堆的应用-优先级队列

优先级队列数据结构：应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。

内部原理：优先级队列的实现方式有多种，但最常见的是使用堆来构建

入队列

首先按尾插方式放入数组
比较其和双亲的值的大小，如果双亲的值大，则满足堆的性质，插入结束
否则，交换其和双亲位置的值，重新进行2,3步骤
直接根节点

	// child是新插入数据的下标public void adjustUp(int child){int parent = (child-1)/2;while (child > 0){if(this.elem[child]>this.elem[parent]){int tmp = this.elem[parent];this.elem[parent] = this.elem[child];this.elem[child] = tmp;child = parent;parent = (child-1)/2;}else {break;}}}public void push(int val){if(ifFull()){this.elem = Arrays.copyOf(this.elem,2*this.elem.length);}this.elem[this.usedSize] = val;this.usedSize++;adjustUp(this.usedSize-1);}private boolean ifFull() {if(this.elem.length == this.usedSize){return true;}else {return false;}}

出队列（出堆顶优先级最高的）

为了防止破坏堆的结构，删除时并不是将堆顶元素删除，而是用数组的最后一个元素替换堆顶元素，然后通过向下调整方式重新调整成堆。

	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--;adjustDown(0,this.usedSize);}public boolean isEmpty(){return this.usedSize==0;}

返回队首元素

	public int peek(){if(isEmpty()){// return -1;throw new RuntimeException();}return this.elem[0];}

堆的其他应用-TopK问题

问题：给100万个数据排序，取前10个最大的

基本思路：直接Array.sort();
建立一个堆，这个堆是大堆，取前10个。缺点是堆太大了，堆大小也是100万。
建立一个大小为K的小堆。将当前数组的前K个建立为小堆；遍历剩下的元素，依次和堆顶元素比较，如果当前i下标元素比堆顶元素大，就把i下标入队。

相反，如果找前K个最小的，建堆就是大堆。

从数组中找最小的K个数据

    public static void topK(int[] array,int k){PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}});// 建立大堆for (int i = 0; i < array.length; i++) {if(maxHeap.size() < k){// 优先级队列会自动调整为大堆maxHeap.offer(array[i]);}else {int top = maxHeap.peek();if (top > array[i]){maxHeap.poll();maxHeap.offer(array[i]);}}}System.out.println(maxHeap);}

堆的其他应用-堆排序

从小到大排序建立大堆

	public void heapSort(){int end = this.usedSize-1;while (end>0){int tmp = this.elem[0];this.elem[0] = this.elem[end];this.elem[end] =tmp;adjustDown(0,end);end--;}}

从大到小排序建立小堆

LeetCode373. 查找和最小的 K 对数字

class Solution {public List<List<Integer>> kSmallestPairs(int[] nums1,int[] nums2,int k){PriorityQueue<List<Integer>> maxHeap = new PriorityQueue<>(k, new Comparator<List<Integer>>() {@Overridepublic int compare(List<Integer> o1, List<Integer> o2) {/*** o2 和 o1 存的是List的引用* */// o2 -o1 的变形return (o2.get(0)+o2.get(1)) - (o1.get(0)+o1.get(1));}});for (int i = 0; i < nums1.length; i++) {for (int j = 0; j < nums2.length; j++) {if(maxHeap.size()<k){List<Integer> pair = new ArrayList<>();pair.add(nums1[i]);pair.add(nums2[j]);maxHeap.offer(pair);}else {List<Integer> top = maxHeap.peek();// 如果当前元素 比 堆顶小 就弹出堆顶 然后将小的数据放入堆int topValue = top.get(0)+top.get(1);if(topValue > nums1[i]+nums2[j]){maxHeap.poll();List<Integer> pair = new ArrayList<>();pair.add(nums1[i]);pair.add(nums2[j]);maxHeap.offer(pair);}}}}List<List<Integer>> ret = new ArrayList<>();for (int i = 0; i < k && !maxHeap.isEmpty(); i++) {// 将堆弹出的元素放到ret中ret.add(maxHeap.poll());}return ret;}
}