数据结构之优先级队列

发布于：2025-03-29 ⋅ 阅读:(29) ⋅ 点赞:(0)

1.概念

1.1优先级队列：

能够提供两个基本操作1️⃣返回最高优先级对象2️⃣添加新的对象

底层是顺序存储的二叉树（完全二叉树--调整-》堆）

1.2堆：

  • 小根堆：根节点小于左右孩子的完全二叉树
  • 大根堆：           大于

其存储结构存储的堆层序遍历的值，并且下标的规律：

  1. 已知孩子节点下标为i，那么父亲节点下标为（i - 1）/2；
  2. 已知父亲节点下标为i   那么左：2*i+1   右：2*i+2

2.堆的创建（模拟实现）

2.1堆向下调整

思路：

1.找到最后一棵子树的根节点p = (len-1 -1)/2，p--就能把每颗子树都调整结束

2.如何向下调整呢？

1️⃣引入c左孩子下标，比较左右孩子，c一定是最大值下标

2️⃣比较c与p，若c>p 交换  ；若c<p 打断

3️⃣最重要的一步：让p = c，c=2p+1，向下调整

public class TestHeap{
    private int[] elem;

    private int usedSize;

    public TestHeap(){//构造方法
        this.elem = new int[10];
    }

    public void initHeap(int[] array){
        for(int i = 0;i< array.length;i++){
            elem[i] = array[i];
            usedSize++;
        }
    }
    public void createHeap(){
        for(int parent = (usedSize -1-1)/2;parent >= 0;parent--){//找到根节点
            shiftDown(parent,usedSize);
        }
    }
    //每一颗子树都向下调整
    private void shiftDown(int parent, int usedSize) {
        int child = (2*parent)+1;//左孩子下标
        while(child < usedSize){
            if(child+1 < usedSize && elem[child] <elem[child+1]){
                child++;
            }
            //child一定是左右孩子最大值的下标
            if(elem[child] > elem[parent]){
                swap(child,parent);
                parent = child;
                child = 2*parent+1
            }else{
                //已经是大根堆了
                break;
            }
        }
    }

    private void swap(int i,int j){
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }

}

2.2.向下建堆的时间复杂度

当我们采用向下调整去建堆的时候，时间复杂度为O(n)

公式须知 

1.等比数列求和公式  a1(1-q^n)/(1-q)

2.n个节点= 2^h-1  (h是树的高度）

3.h = log2(n+1)

3.堆的插入与删除

3.1堆的插入

问题：

1.80往哪里放？

2.放进去怎么放到合适的位置？向上调整

思路：

1.插入前先判断是否需要扩容

2.把要插入的元素放在最后一个位置

3.向上调整

1️⃣确定最后一个根节点p

2️⃣比较c和p，若c>p 交换   否则  打断

3️⃣让c=p，p=(c-1)2   向上调整，如此循环

/*插入元素   向上调整*/
    public void offer(int val){
        if(isFull()){
            this.elem = Arrays.copyOf(elem,2*elem.length);
        }
        this.elem[usedSize] = val;//把要插入的元素放在最后一个位置
        //向上调整
        shiftUp(usedSize);
        usedSize++;

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

    private boolean isFull(){
        return usedSize == elem.length;
    }

}

向上调整的复杂度比向下调整高，向上调整建堆的时间复杂度为O(N*logN)

向下排序  复杂度是O(n)

向上排序  复杂度O(nlogn)

3.2堆的删除

堆的删除一定删除的是堆顶元素

思路：

1. 先保存堆顶元素的数值，将堆顶元素和堆中最后一个元素交换

2. 将堆中有效数据个数减少一个

3. 对堆顶元素进行向下调整

 /*删除元素*/
    public int poll(){
        int tmp = elem[0];
        swap(0,usedSize-1);
        usedSize--;
        shiftDown(0,usedSize);
        return tmp;
    }

 测试代码：

public class Test {
    public static void main(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        testHeap.initHeap(array);

        testHeap.createHeap();
        

        testHeap.offer(80);
        int val = testHeap.poll();
        System.out.println(val);

    }
}

3.3习题

已知小根堆为8,15,10,21,34,16,12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较次数是()

A: 1     B: 2     C: 3   D: 4

答案：C

1.15 和10比较一次

2.10和12比较一次

3.12和16比较一次

4.常用接口介绍

4.1PriorityQueue的特性

1. 使用时必须导入PriorityQueue所在的包，即：

import java.util.PriorityQueue;

 2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出 ClassCastException异常（类型转换异常，不能够转换成Comparable类型）

3. 不能插入null对象，否则会抛出NullPointerException（空指针异常）

4. 插入和删除元素的时间复杂度为O(log2N)  【树的高度】 

5.PriorityQueue底层使用了堆数据结构

6. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素

4.2PriorityQueue常用接口介绍（重在理解）

4.2.1优先级队列的构造

  • 创建一个空的优先级队列，底层默认容量是11

 PriorityQueue<Integer> q1 = new PriorityQueue<>();

  • 创建一个空的优先级队列，底层的容量为initialCapacity

PriorityQueueInteger> q2 = new PriorityQueue<>(100);

  • 用一个集合来创建优先级队列（PriorityQueue(Collection<?extends E>c)  只要实现Collection接口的所有对象都能传）

ArrayListInteger> list = new ArrayList<>();  

list.add(4);        

list.add(3);        

list.add(2);        

list.add(1);        

// 用ArrayList对象来构造一个优先级队列的对象        

// q3中已经包含了三个元素        

PriorityQueueInteger> q3 = new PriorityQueue<>(list);        

System.out.println(q3.size());        

System.out.println(q3.peek());

默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器

4.2.2插入/删除/获取优先级最高的元素

4.2.3优先级队列的扩容方式：

  • 如果容量小于64时，是按照oldCapacity的2倍方 式 扩 容 的
  • 如果容量大于等于64 ，是按照oldCapacity的1.5倍方 式 扩 容 的
  • 如果容量超过MAX_ARRAY_SIZE（整数的最大值-8）， 按 照 MAX _ARRAY_ SIZE 来 进 行 扩 容（按照整数的最大值来算，也就是多加8个） 

5.堆的应用✨

5.1.oj例题

import java.util.PriorityQueue;

class Solution{
    public int[] smallestK(int[] array,int k){
        int[] ret = new int[k];
        if(array == null||k<=0){
            return ret;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(array.length);
        
        for(int i = 0;i< array.length;i++){
            priorityQueue.offer(array[i]);
        }
        for(int i= 0;i<k;i++){
            ret[i] =priorityQueue.poll();
        }
        return ret;
    }
}

5.2Top-K问题

求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大

做法1：把数组排序 排序之后 取出前10个最大的  数据量非常大的时候，你无法在内存当中排序

做法2：把所有数据 放到优先级队列 出队k次不就好了？数据量非常大的时候，你无法把所有数据放到优先级队列！

求前k个最大的数据建议的做法：

1.前k个数据，小根堆k，堆顶是这k个元素里面的最小值

2.把剩下的元素 每次和堆顶元素比较，如果比堆顶大 那么出队 然后把当前数组元素存放到大小为k的堆当中（i下标的元素如果大于堆顶元素 那么说明堆顶元素一定不是前k个最大的元素之一）

时间复杂度：O（K*logK）+O((N-K)*logK)=O(N*logK)

import java.util.PriorityQueue;

class Solution{
    public int[] naxLestK(int[] array,int k){
        int[] ret = new int[k];
        if(array == null||k<=0){
            return ret;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(array.length);
        for(int i = 0;i<k;i++){
            priorityQueue.offer(array[i]);

        }
        for(int i = k;i<array.length;i++){
            int top = priorityQueue.peek();
            if(array[i]>top){
                priorityQueue.poll();
                priorityQueue.offer(array[i]);
            }
        }
        for(int i = 0;i<k;i++){
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }
}

求前K个最小的数据 要建大根堆！

o1-o2小根堆

o2-o1大根堆

import java.util.Comparator;
import java.util.PriorityQueue;
class IntCmp implements Comparator<Integer>{
    public int compare(Integer o1,Integer o2){
        return o2.compareTo(o1);//重写compare方法
    }
}
class Solution{
    public int[] smallestK(int[] array,int k){
        int[] ret = new int[k];
        if(array == null||k<=0){
            return ret;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new IntCmp());
        for(int i = 0;i<k;i++){
            priorityQueue.offer(array[i]);

        }
        for(int i = k;i<array.length;i++){
            int top = priorityQueue.peek();
            if(array[i]<top){
                priorityQueue.poll();
                priorityQueue.offer(array[i]);
            }
        }
        for(int i = 0;i<k;i++){
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }
}

找第K大的元素  建的是小根堆，就是堆顶元素

找第K小的元素  建的是大根堆，就是堆顶元素

5.3.堆排序

应用背景：
一组数据：[27,15,19,18,28,34,65,49,25,37]  将其从小到大进行排序（对原来的数据进行排序！！！不可以让其变成小根堆，然后一个一个取数据）

升序：建大堆
降序：建小堆

思路：

1.调整为大根堆

2.让第一个元素和最后一个未排序的元素进行交换

 

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

 5.4习题

一组记录排序码为 (5 11 7 2 3 17)， 则利用堆排序方法建立的初始堆为 ()
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)
答案：C
解析：没说升序还是降序，根据选项，5不在前，说明是大根堆，所以本题考察的是如何建大根堆

6.java对象的比较

  • Comparable（对类的侵入性比较强，写好了就不能改了）不如Comparator（可以根据自己的逻辑实时调整思路）灵活，共同点是两者返回的都是整数，可以比较大小
  • equals  返回值是boolean  比较这两个对象是否相同（必须要重写equals方法，否则还是和==一样，比较的是地址）
import java.util.Objects;

class Student{
    public String name;
//右键generate  equals and hashCode可自动生成
    public boolean equals(Object obj) {
        
        Student o = (Student)obj;
        return o.name.equals(this.name);
    }
}
public class Test{
    public static void main(String[] args) {
        Student student1 = new Student();
        student1.name = "zhangsan";
        Student student2 = new Student();
        student2.name = "zhangsan";

        System.out.println(student1==student2);//输出结果为false
        System.out.println(student1.equals(student2));//若是不重写equals，还是false

    }

}

网站公告

今日签到

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

热门文章

最新发布