堆的概念
堆的分类:堆又称为优先队列和优先级队列,顾名思义,其进出堆的方式就是先进先出(FIrst In First Out),堆可以分为大根堆和小根堆
根据上图,堆的底层实现就是一颗二叉树,且是一颗完全二叉树,但是不一样的地方是,这个完成二叉树有着特定的排列规则,当堆为大根堆时,其顶上根中的值是最大的值,每颗子树同样满足这一特点,左右结点都比根结点的值要小。且可以看出越小的值跟靠近顶上的根节点,但是也不一定,,小根堆相反。
堆的顺序储存
顺序结构是通过数组来实现,顺序结构为了防止造成空间浪费,一般适合完全二叉树,而堆结构其底层就是完全二叉树,所以用数组来储存堆。所以堆在物理物理储存上,是数组,在逻辑上,是一颗完全二叉树,所以遍历二叉树的时候,最好用层序遍历
可以看出完全二叉树用顺序存储,数组相对于非完全二叉树来说,可以充分利用,防空间的浪费,非完全二叉树不能充分利用其空间,顺序储存时,就会造成间隙,没有利用的空间
创建堆结构
public void createHeap(int[] array){
//初始化堆中的元素
for (int i = 0; i < array.length; i++) {
elem[i] = array[i];
usedSize++;
}
for (int p = (usedSize - 1 -1) / 2; p >= 0 ; p-- ) {
shiftDown(p,usedSize);
}
}
/**
*
* @param root 是每棵子树的根节点的下标
* @param len结束条件
*/
private void shiftDown(int root,int len){ //向下调整
int parent = root;
int child = 2*parent+1;
while(child < len){
if(child+1 < len && elem[child] < elem[child+1]){
child++;
}
if(elem[child] > elem[parent]){
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
parent = child;
child = 2*parent+1;
}else{
break;
}
}
}
入队(offer)
public void push(int val){
if(isFull()){
elem = Arrays.copyOf(elem,2*elem.length);
}
//放到最后位置
elem[usedSize] = val;
//进行向上调整
shiftUp(usedSize);
//有效数字加一
usedSize++;
}
public void shiftUp(int child){
int parent = (child-1) / 2;
while(child > 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;
}
}
}
public boolean isFull(){
return usedSize == elem.length;
}
出堆(poll)
public void pollHeap(){
if(isEmpty()){
System.out.println("优先级队列为空");
return;
}
int tmp = elem[0];
elem[0] = elem[usedSize - 1];
elem[usedSize-1] = tmp;
usedSize--;
shiftDown(0,usedSize);
}
public boolean isEmpty(){
return usedSize == 0;
}
查看堆顶元素
public int peekHeap(){
if(isEmpty()){
System.out.println("优先级队列为空");
return -1;
}
return elem[0];
}
堆的应用
用于解决topk问题
问题:设计一个算法,找出数组中最小的k个数。以任意顺序返回这k个数均可。
输入: arr = [1,3,5,7,2,4,6,8], k = 4
输出: [1,2,3,4]
思路:
- 求最小的k个数,先建大根堆;如果求最大的k个数,先建立小根堆。
- 如果求最小的k个数,这时候需要我们重写Comparator中的compare方法,因为PriorityQueue源码中已经实现了compare方法,且只能建立小根堆。
注意事项:这里输入的k个数,k的不能为零,否则会报错,这时候需要单独判断零的情况 - 先将数组中的元素放满k个数到堆中,然后用数组中剩下元素与根结点进行比较,如果这个值小于根结点的值,则把它与根节点交换,堆内部就会重写形成一个新的堆,循环走完整个数组,就可以得到最小的k个元素。
class IntCmp implements Comparator<Integer>{
@Override
public int compare(Integer o1,Integer o2){
return o2 - o1;
}
}
class Solution {
public int[] smallestK(int[] arr, int k) {
if(k == 0){
return new int[k];
}
IntCmp intCmp = new IntCmp();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k,intCmp);
for(int i = 0; i < arr.length; i++){
if(maxHeap.size() < k){
//说明没放满
maxHeap.offer(arr[i]);
}else{
int top = maxHeap.peek();
if(arr[i] < top){
maxHeap.poll();
maxHeap.offer(arr[i]);
}
}
}
int[] ret = new int[k];
for(int i = 0; i < k; i++){
int val = maxHeap.poll();
ret[i] = val;
}
return ret;
}
}
用于排序
//从小到大排序,则建立大根堆
public void heapSort(){
int end = usedSize - 1;
while(end > 0){
int tmp = elem[0];
elem[0] = elem[end];
elem[end] = tmp;
shiftDown(0,end);
end--;
}
}