数据结构之【堆】(Heap)

目录

1. 优先级队列(Priority Queue)

2.堆的概念

3.堆的存储方式

4.堆的创建

5.用堆模拟实现优先级队列

 6.PriorityQueue常用接口介绍

6.1 PriorityQueue的特点

6.2 PriorityQueue几种常见的构造方式

7.top-k问题

8.堆排序


本篇主要内容总结

(1)优先级队列底层是堆来实现的

(2)堆的本质是完全二叉树  ,堆有大根堆和小根堆

(3)大根堆:根节点最大的堆; 小根堆:根节点最小的堆

(4)堆的创建实现:大根堆为例

大根堆创建:孩子结点和根节点比较交换,核心思想:向下调整   时间复杂度O(n)

堆的插入:插入到最后一个位置,和根结点交换,核心思想:向上调整

堆的删除:只能删除堆顶,然后重新向下调整组成新的大根堆

插入和删除时间复杂度O(log n)

(4)priorityQueue建堆是小根堆,如果要建立大根堆就要写比较器

(5)priorityQueue添加元素,要写明比较的类型才能添加

(6)top-K问题:前K个最大的元素建小根堆;前K个最小的元素建大根堆

第K个最大元素建小根堆 拿栈顶;    第K个最小元素建大根堆 拿栈顶

(7)堆排序:升序:大根堆    降序:小根堆

核心思想:堆元素的删除


 

在说堆的概念之前,先说一下堆的常用方法,从这个方向来写这篇文章

堆的常用方法有

(1)用来构建优先级队列

(2)支持堆排序(大堆或小堆)

(3)top-k问题


1. 优先级队列(Priority Queue)

优先级队列 :是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。

优先级队列相对于普通队列应该提供两个最基本的操作,

(1)返回最高优先级对象(2)添加新的对象

在JDk1.8中的优先级队列底层使用了堆

2.堆的概念

简单的说 ,堆这种数据结构本质上就是一个完全二叉树

并且堆中某个结点的值总是不大于或不小于其父结点的值

小堆:根节点最小的堆,满足Ki <= K2i+1 且 Ki <= K2i+2 

大堆:根节点最大的堆,   满足Ki >= K2i+1 且 Ki >= K2i+2 

3.堆的存储方式

堆是一颗完全二叉树,所以按照层序来看,可以采用顺序数组的存储方式

但是非完全二叉树就不适用于顺序存储了,这是因为非完全二叉树如果有空结点,那顺序存储也要存储这个空节点,这就造成空间上的浪费

i表示孩子结点,父亲结点(i-1)/ 2

i表示根节点 ,左孩子 2 * i + 1    右孩子   2 * i + 2

4.堆的创建

5.用堆模拟实现优先级队列

按照大根堆来创建

先写一个数组,按顺序存储的方式

    public int[] elem;
    public int userSize;//当前堆中有效的元素数据个数

    public MyHeap() {
        this.elem = new int[10];
        this.userSize = 0;
    }

    public void initArray(int[] array) {
        elem = Arrays.copyOf(array,array.length);
        userSize = elem.length;
    }

(1) 创建堆

先写一个向下调整的方法

  /**
     * @param parent: 每颗子树的根节点下标
     * @param len:每颗子树的结束位置
     * @description 向下调整
     */
    private void shiftDown(int parent,int len) {
        int child = 2*parent+1;//左孩子
        //必须要有左孩子
        while(child < len) {
            //如果一定有右孩子。那就判断 左孩子和右孩子大小,谁大保存谁
            if(child + 1 < userSize && elem[child] < elem[child+1]) {
                child++;
            }
            //交换 比较孩子和根大小交换 然后根节点往下走继续必须
            if (elem[child] > elem[parent]) {
                swap(elem,child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

再写一个交换根和孩子的方法

    //交换  比较孩子和根大小交换
    private void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

然后通过循环每个结点,向下调整,然后创建好这棵树

    /**
     *建堆:大根堆
     *时间复杂度O(n)
     */
    public void createHeap() {
        for (int parent = (userSize-1-1)/2; parent >= 0 ; parent--) {
            shiftDown(parent,userSize);
        }
    }

分析一下建堆的时间复杂度O(n)


 (2)堆的插入

先写一个方法来判断空间满不满

    public boolean isFull() {
        return userSize == elem.length;
    }

再写一个向上调整

 //向上调整
    private void shiftUp(int child) {
        int parent = (child - 1) / 2;
        while(child > 0) {
            if(elem[child] > elem[parent]) {
                swap(elem,child,parent);
                child = parent;
                parent = (child - 1) / 2;
            }else {
                break;
            }
        }
    }

 最后再写堆的插入,如果空间满了就扩容,然后再向上调整,变成新的大根堆

    //堆的插入
    public void offer(int x) {
        if (isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        this.elem[userSize] = x;
        userSize++;
        shiftUp(userSize-1);
    }

 (3)堆的删除(优先级队列删除,只能删除堆顶的元素)

再删除前,先要看堆是不是空的

    public boolean isEmply() {
        return userSize == 0;
    }

然后再删除堆顶元素

  //堆的删除  只能删除堆顶元素
    public int poll() {
        if (isFull()) {
            return -1;
        }
        int old = elem[0];
        //1.交换
        swap(elem,0,userSize-1);
        //2.有效元素个数-1
        userSize--;
        //3.栈顶元素向下调整
        shiftDown(0,userSize);
        return old;
    }

看几个选择题把 

1.已知小根堆为8,15,10,21,34,16,12,删除关键字8之后需重建堆,在此过程中,关键字之间的比较次数是     (C)
A: 1 B: 2 C: 3 D: 4

2.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后,其结果是    ()

A: [3 2 5 7 4 6 8] B: [2 3 5 7 4 6 8]
C: [2 3 4 5 7 8 6] D: [2 3 4 5 6 7 8]

 6.PriorityQueue常用接口介绍

6.1 PriorityQueue的特点

(1)首先最重要的先明白priorityQueue建堆是小根堆

    public static void main(String[] args) {
        //默认是小根堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(45);
        priorityQueue.offer(12);
        priorityQueue.offer(55);
        priorityQueue.offer(66);
        System.out.println(priorityQueue.peek());
    }

可以看到这里打印的是12所以是priorityQueue是小根堆

如果要建堆为大根堆,那就要写比较器Comparator了 

    public static void main(String[] args) {
       PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
           @Override
           public int compare(Integer o1, Integer o2) {
               return o2-o1;
           }
       });
    }

 

(2) 在priorityQueue使用offer添加元素时,一定要明确比较的规则,然后再添加

如果是直接这样比较的话,offer不知道以什么规则比较然后添加,就会报错。 

    public static void main(String[] args) {
        PriorityQueue<Fruit> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(new Fruit() );
        priorityQueue.offer(new Fruit() );
    }

所以这里必须告诉offer以什么方式比较添加,

比如说这里实现comparable接口

class Fruit implements Comparable<Fruit>{
    public int age;
    //必须告诉priorityQueue.offer 以什么方式比较添加元素
    @Override
    public int compareTo(Fruit o) {
        return this.age - o.age;
    }
}

(3)不能插入null对象,否则会抛出NullPointerException异常

(4)可以插入任意多个元素,会自动扩容,没有容量限制

 

 (5)插入和删除元素的时间复杂度为O(log n),建栈的时间复杂度O(n)


6.2 PriorityQueue几种常见的构造方式

(1)PriorityQueue()   初始默认容量为11

(2)PriorityQueue(int initialCapacity)

(3)PriorityQueue(Collection<? extends E> c)

 

(4)PriorityQueue(int initialCapacity, Collection<? super E> comparator


7.top-k问题

适用情况,在数据量比较大时,求数据集合中前K个最大的元素或者最小的元素

比如说求很多个元素的前k个最大的元素 

思路1:

(1)将这些元素,全部放进大根堆中,堆顶的元素就是最大的值

(2)然后出k次,就能得到前k个最大的值,并且每出一次都会进行向下调整,变成新的大根堆

 public static void topK1(int[] array, int k) {
        PriorityQueue<Integer> maxPQ = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });

        for (int i = 0; i < array.length; i++) {
            maxPQ.offer(array[i]);
        }
        for (int i = 0; i < k; i++) {
            int val = maxPQ.poll();
            System.out.println(val);
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] array = {16,15,22,155,89,12,45};
        topK1(array,3);
    }

 

 缺点:数字有多少,这个堆就有多大,时间复杂度是O(n*log n)

 思路2:

(1)求前K个最大的元素,建立大小为K的小根堆

(2)然后用剩下的集合里面的元素轮流和堆顶元素比较,如果剩下集合里面的元素比堆顶的元素大,那就替换掉堆顶的元素

(3)然后向下调整,变成新的小根堆,此时这个堆中的元素就是前K个最大元素

1. 那如果要求前K个最小的元素,如何做
差不多和前面一样的方法,不同的是
(1)求前K个最小的元素,要建立大根堆
(2)比较的时候谁小,就把小的放在堆顶

 力扣链接:   面试题 17.14. 最小K个数 - 力扣(LeetCode)

class Solution {
    public int[] smallestK(int[] arr, int k) {
       int[] ret = new int[k];
        if(k == 0) return ret;
        PriorityQueue<Integer> maxPQ = new PriorityQueue<>(k,new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });

        for (int i = 0; i < arr.length; i++) {
            if(maxPQ.size() < k) {
                maxPQ.offer(arr[i]);
            }else {
                //获取到堆顶元素
                int top = maxPQ.peek();
                //找前k个最小的
                if(arr[i] < top) {
                    maxPQ.poll();
                    maxPQ.offer(arr[i]);
                }
            }
        }
        for (int i = 0; i < k; i++) {
            ret[i] = maxPQ.poll();
        }
        return ret;
    }
}
2. 那如果要求第K大的元素,或者第K小的元素如何做
(1)前面求前K个最大的元素时,建立的小根堆,按照规则,到最后栈中全部都是前K个最大的元素,然后栈顶就是所要求得的第K大的元素
(2)前面求前K个最小的元素时,建立的大根堆,按照规则,到最后栈中全部都是前K个最小的元素,然后栈顶就是所要求得的第K小的元素

8.堆排序

 如果是将堆排成一个升序的,那就建立大根堆,操作如下

    public void heapSort() {
        int end = userSize -1;
        while(end > 0) {
            swap(elem,0,end);
            shiftDown(0,end);
            end--;
        }
    }

 

如果是将堆排成一个降序的,那就建立小根堆,操作和上面类似

一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为  (C)
A: (11 5 7 2 3 17) B: (11 5 7 2 17 3) C: (17 11 7 2 3 5)
D: (17 11 7 5 3 2) E: (17 7 11 3 5 2) F: (17 7 11 3 2 5)

 

 



文章标签:

原文连接:https://blog.csdn.net/m0_58761900/article/details/125804593

相关推荐

坚持用C++刷牛客题(剑指offer专题)

简答一波 HashMap 常见八股面试题 —— 算法系列(2)

LeetCode周赛302,这也太卷了,20分钟ak也只有300名……

「Java数据结构」手撕数组队列及环形数组队列。

挑战全网最详细讲解 平衡二叉树 AVL,手把手带你手撕 AVL !!!

【数据结构】插入排序(直接插入排序 && 希尔排序)

【C语言进阶】自定义类型——结构体

洛谷每日三题之第六天

【27. 表达式求值(中缀表达式)】

数据结构之【堆】(Heap)

经典TopK问题、优先级队列 与 堆的纠葛一文为你解惑——数据结构

2022-7-15 java 数据结构入门

树状数组

Java | 平铺列表(List)互转树形(Tree)结构

算法秒懂之背包问题(DP)-附牛客网真题实战

【二叉树】之力扣牛客必刷题

求数据流中的中位数问题

字典树及其实现

【数据结构】栈实现队列 & 队列实现栈

python查找与排序算法详解(示意图+代码、看完基础不成问题)