数据结构——优先级队列(堆)

发布于:2023-01-04 ⋅ 阅读:(643) ⋅ 点赞:(0)

堆的概念

堆的分类:堆又称为优先队列和优先级队列,顾名思义,其进出堆的方式就是先进先出(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--;
        }
    }

网站公告

今日签到

点亮在社区的每一天
去签到