目录
- 1. 相关概念
- 2. PriorityQueue的实现
- 2.0 搭建整体框架
- 2.1 堆的创建和调整
- 2.2 插入元素
- 2.3 出堆顶元素
- 3. 全部代码（包含大根堆和小根堆）
- 4. PriorityQueue的使用
- 5. Top-K问题
之前我们学习的二叉树的存储方式是链式存储，（不清楚的可以看这篇哦： 二叉树），而堆是二叉树的另一种存储方式：顺序存储，jdk1.8中的优先级队列： PriorityQueue 的底层就是使用了堆这种数据结构
1. 相关概念
堆，可以认为是一棵使用顺序存储的方式来存储数据的一棵完全二叉树，堆分为大根堆和小根堆
大根堆：每个结点的值都不小于左右孩子结点的值
小根堆：每个结点的值都不大于左右孩子结点的值
如图：
复习：
如果父亲结点是i下标：左孩子2i+1；右孩子2i+2
如果孩子结点是i下标：父亲（ i-1）/ 2（不管i是左孩子还是右孩子）
2. PriorityQueue的实现
PriorityQueue默认是小根堆，所以我们也实现一个小根堆，文章最后会给出大根堆和小根堆的全部代码哦
2.0 搭建整体框架
定义一个Heap类
public class Heap {
public int[] elem;//存储数据的数组
public int curSize;//当前数据的个数
}
2.1 堆的创建和调整
当拿到一组数据后如：2、4、3、9、6、1、5，如何将这组数据调整为小根堆？先将数据按层序遍历的方式，画出一棵二叉树，如图：
从最后一棵子树开始调整，循环直到整棵树都是小根堆
//创建堆(小根堆)
public void createHeap() {
for (int parent = (elem.length - 1 - 1) / 2; parent >= 0; parent--) {
shiftDown(elem, parent, elem.length);
}
}
//向下调整的逻辑:
private void shiftDown(int[] array, int parent, int end) {
int child = (parent * 2) + 1;
while (child < end) {
if (child + 1 < end && array[child] > array[child + 1]) {
child++;
}
//保证child下标是最小的
if (array[child] < array[parent]) {
//交换child下标和parent下标的值
int tmp = array[child];
array[child] = array[parent];
array[parent] = tmp;
//
parent = child;
child = parent * 2 + 1;
} else {
break;//已经是小根堆了,结束循环
}
}
}
如何调整?拿parent=0举例
如图：调整
以下是进行一次调整的逻辑，对每棵子树都进行向下调整，整棵树就能变成小根堆
2.2 插入元素
插入是在数组的最后一个元素之后插入，插入之后的堆中的最后一个元素定义为child，child和它的父亲比较，将较小的做为根节点，接着
public void offer(int key) {
if (curSize == elem.length) {
//扩容
elem = Arrays.copyOf(elem, elem.length * 2);
}
elem[curSize] = key;
curSize++;
shiftUp(curSize - 1);
}
//向上调整
public void shiftUp(int child) {
int parent = (child - 1) / 2;
while (parent >= 0) {
if (elem[child] > elem[parent]) {
//交换
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
child = parent;
parent = (child - 1) / 2;
} else {
break;
}
}
}
2.3 出堆顶元素
将堆顶元素和最后一个元素交换，前有效数据个数-1，接着将删除后的堆进行向上调整
public int pool() {
int ret = elem[0];
swap(elem, 0, curSize - 1);
curSize--;
shiftDown(elem, 0, curSize);
return ret;
}
3. 全部代码（包含大根堆和小根堆）
public class Heap {
public int[] elem;//存储数据的数组
public int curSize;//当前数据的个数
public Heap(int[] array) {
//构造方法,初始化时给elem数组
elem = new int[10];
for (int i = 0; i < array.length; i++) {
elem[i] = array[i];
curSize++;
}
}
//创建堆(大根堆)
public void createMaxHeap(int[] array) {
for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
shiftDownMax(elem, parent, array.length);
}
}
//创建堆(小根堆)
public void createMinHeap(int[] array) {
for (int parent = (elem.length - 1 - 1) / 2; parent >= 0; parent--) {
shiftDownMin(elem, parent, elem.length);
}
}
//向下调整:大根堆
private void shiftDownMax(int[] array, int parent, int end) {
int child = (parent * 2) + 1;
while (child < end) {
if (child + 1 < end && array[child] < array[child + 1]) {
child++;
}
//child是最大的
if (array[child] > array[parent]) {
swap(array, child, parent);
parent = child;
child = parent * 2 + 1;
} else {
break;//已经是大根堆了,结束循环
}
}
}
//向下调整:小根堆
private void shiftDownMin(int[] array, int parent, int end) {
int child = (parent * 2) + 1;
while (child < end) {
if (child + 1 < end && array[child] > array[child + 1]) {
child++;
}
//child是最大的
if (array[child] < array[parent]) {
swap(array, child, parent);
parent = child;
child = parent * 2 + 1;
} else {
break;//已经是小根堆了,结束循环
}
}
}
/**
* 插入数据,大根堆
*
* @param key
*/
public void offerMax(int key) {
if (curSize == elem.length) {
//扩容
elem = Arrays.copyOf(elem, elem.length * 2);
}
elem[curSize] = key;
curSize++;
shiftUpMax(curSize - 1);
}
/**
* 插入数据,小根堆
*
* @param key
*/
public void offerMin(int key) {
if (curSize == elem.length) {
//扩容
elem = Arrays.copyOf(elem, elem.length * 2);
}
elem[curSize] = key;
curSize++;
shiftUpMin(curSize - 1);
}
/**
* 删除数据,大根堆
*
* @return
*/
public int poolMax() {
if (isEmpty()) {
return -1;
}
int ret = elem[0];
swap(elem, 0, curSize - 1);
curSize--;
shiftDownMax(elem, 0, curSize);
return ret;
}
/**
* 删除数据,小根堆
* @return
*/
public int poolMin() {
if (isEmpty()) {
return -1;
}
int ret = elem[0];
swap(elem, 0, curSize - 1);
curSize--;
shiftDownMin(elem, 0, curSize);
return ret;
}
//向上调整,大顶堆
private void shiftUpMax(int child) {
int parent = (child - 1) / 2;
while (parent >= 0) {
if (elem[child] > elem[parent]) {
swap(elem, parent, child);
child = parent;
parent = (child - 1) / 2;
} else {
break;
}
}
}
//向上调整,大顶堆
private void shiftUpMin(int child) {
int parent = (child - 1) / 2;
while (parent >= 0) {
if (elem[child] < elem[parent]) {
swap(elem, parent, child);
child = parent;
parent = (child - 1) / 2;
} else {
break;
}
}
}
//交换
private void swap(int[] arr, int x, int y) {
int tmp = arr[x];
arr[x] = arr[y];
arr[y] = tmp;
}
@Override
public String toString() {
StringBuilder str = new StringBuilder();
for (int i = 0; i < curSize; i++) {
str.append(elem[i]);
if (i != curSize - 1) {
str.append(", ");
}
}
return str.toString();
}
//判断是否为空
private boolean isEmpty() {
return curSize == 0;
}
}
4. PriorityQueue的使用
PriorityQueue的插入、删除的方法名和我们实现的一样这里不多赘述，Java中的PriorityQueue默认是小根堆，如果想变成大根堆，需要在实例化时传入自己实现的比较器
class Com implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;//大堆
}
}
public static void main(String[] args) {
PriorityQueue<Integer> queue = new PriorityQueue<>(new Com());
queue.offer(1);
}
今天的内容就到这里~感谢大家的支持！
5. Top-K问题
Top-K问题是求一个数据集合中，前K个最大值或者最小值，例如班级排名前十、世界五百强等。我们很容易想到将数据进行排序，但是当数据量比较大时，排序的效率很低，而且并不能将数据全部加载到内存中，那么怎么解决这个问题？最好的办法就是使用堆。
求前K个最大的元素： 建一个大小为K的小堆，剩下的N-K个元素与堆顶比较，将不符合要求的元素替换掉
求前K个最小的元素： 建一个大小为K的大堆，剩下的N-K个元素与堆顶比较，将不符合要求的元素替换掉
例题：最小K个数
class intCmp implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
}
class Solution {
public int[] smallestK(int[] arr, int k) {
PriorityQueue<Integer> queue = new PriorityQueue<>(new intCmp());
int[] ret = new int[k];// 要返回的数组
if (k == 0) {
return ret;
}
// 建大小为k的大根堆
for (int i = 0; i < k; i++) {
queue.offer(arr[i]);
}
for (int i = k; i < arr.length; i++) {
int val = queue.peek();
if (val > arr[i]) {
queue.poll();
queue.offer(arr[i]);
}
}
for (int i = 0; i < k; i++) {
ret[i] = queue.poll();
}
return ret;
}
}
