堆的概念
- 堆逻辑上是一棵完全二叉树
- 堆物理上是保存在数组中
- 满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆
- 反之，则是小堆，或者小根堆，或者最小堆
- 堆的基本作用是快速找集合中的最值
二叉树的顺序存储
使用数组保存二叉树结构，方式即将二叉树用层序遍历方式放入数组中。
一般只适合表示完全二叉树，因为非完全二叉树会有空间的浪费。
这种方式的用法就是堆的表示。
顺序存储中的双亲与孩子的下标关系
已知双亲的下标：
- 左孩子下标 = 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++) {
// 把数组的值拷贝给 elem
this.elem[i] = array[i];
this.usedSize++;
}
// parent 就代表每棵子树的根节点
// 如何拿到最后 最后一个节点的下标: array.length-1
// 最后一个节点的父节点: (array.length-1-1)/2
for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {
// 注意：第2个参数 每次调整的结束位置应该是：不超过数组的最大值，下标不取等于就行
// this.usedSize
adjustDown(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;
// 先移动parent
parent = child;
// 再移动child
child = 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步骤
- 直接根节点
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>() {
@Override
public 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>>() {
@Override
public 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;
}
}