当前位置：首页 > article >正文

Java数据结构第十八期：探索优先级队列的魅力(二)

article 2025/3/19 17:09:31

专栏：Java数据结构秘籍

个人主页：

一、优先级队列常用接口

1.1. 优先级队列的特性

1.2. 优先级队列的使用

1.3. 最小K个数

二、堆的应用

2.1. 堆排序

一、优先级队列常用接口

1.1. 优先级队列的特性

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列， PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的。注意，使⽤PriorityQueue时必须导⼊PriorityQueue所在的包。

import java.util.PriorityQueue;

从上图中我们可以看出，PriorityQueue实现了AbstractQueue接口，我们来看一下PriorityQueue的源码里面继承了AbstractQueue类。而AbstractQueue类里面继承AbstractCollection类和实现了Queue接口。

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {

public abstract class AbstractQueue<E>
    extends AbstractCollection<E>
    implements Queue<E>

插入元素：

import java.util.PriorityQueue;

public class Test {
    public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.offer(10);
        queue.offer(4);
        queue.offer(7);
    }
}

offer的源码如下，从下面的逻辑中可以看出，它的向上调整是一个一个实现的，而不是直接去调整一个数组，所以下面的时间复杂度是 $O(n) = nlogn$ 。

    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        siftUp(i, e);
        size = i + 1;
        return true;
    }

注意事项：

PriorityQueue中放置的元素必须要能够⽐较⼤⼩，不能插⼊⽆法⽐较⼤⼩的对象，否则会抛出 ClassCastException异常。要想实现就必须实现Compareble的接口。

class Student{

}

public class Test {
    public static void main(String[] args) {
        PriorityQueue<Student> queue = new PriorityQueue<>();
        queue.offer(new Student());
    }
}

不能插⼊null对象，否则会抛出NullPointerException。

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

“没有容量限制”，可以插⼊任意多个元素，其内部可以⾃动扩容。
插入和删除的时间复杂度为 $O(n) = nlogn$

1.2. 优先级队列的使用

构造器	功能
PriorityQueue()	创建一个空的优先级队列，默认容量为11
PriorityQueue(int initialCapacity)	创建一个初始容量为initialCapacity的优先级队列
PriorityQueue(Collection<? extends E> c)	用一个集合来创建优先级队列

import java.util.ArrayList;
import java.util.PriorityQueue;

public class Solution {
    public static void main(String[] args) {
        PriorityQueue<Integer> queue1 = new PriorityQueue<>();
        PriorityQueue<Integer> queue2 = new PriorityQueue<>();

        ArrayList<Integer> list = new ArrayList<>();

        list.add(4);
        list.add(3);
        list.add(2);
        list.add(1);

        PriorityQueue<Integer> queue3 = new PriorityQueue<>(list);
        System.out.println(queue3);
    }
}

//PriorityQueue所实现的成员变量，默认容量为11
private static final int DEFAULT_INITIAL_CAPACITY = 11;

PriorityQueue<Character> queue3 = new PriorityQueue<>(list);

如果优先级队列里的泛型不匹配，就会出现报错。我们该如何知道这里的类型呢？我们来看一下PriorityQueue构造方法的源码：Collection可以接受任何类型，后面可以继承它本身的类型或者是它的子类。而上面的Collection接收为ArrayList，E接收为Character，就会产生报错。

    public PriorityQueue(Collection<? extends E> c)

方法名	功能
boolean offer(E e)	插入元素，成功返回true。如果插入元素为空，抛出异常
E peek()	获取优先级最高的元素
E poll()	移除优先级最高的元素并返回
int size()	获取有效元素的个数
void clear()	清空
boolean isEmpty()	检查优先级队列是否为空

public class Solution {
    public static void main(String[] args) {
        PriorityQueue<Integer> queue1 = new PriorityQueue<>();
        queue1.offer(27);
        queue1.offer(15);
        queue1.offer(19);
        queue1.offer(28);
        queue1.offer(34);
        queue1.offer(49);
        System.out.println(queue1);
        System.out.println(queue1.isEmpty());
        System.out.println(queue1.size());

        System.out.println(queue1.peek());
        System.out.println(queue1.poll());
        queue1.clear();
    }
}

public class Solution {
    public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.offer(10);
        queue.offer(5);
    }
}

默认情况下，PriorityQueue队列是⼩堆，如果需要大堆需要用户提供比较器。我们来看一下offer里面sifup所实现的源码。当我们传入一个10的时候，通过Comparable进行强转，在传入数组。方法里面的k作为数组的下标，每传入一个元素，进行比较，而里面的k调用了compareTo接口

    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        siftUp(i, e);
        size = i + 1;
        return true;
    }

    private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x, queue, comparator);
        else
            siftUpComparable(k, x, queue);
    }

    private static <T> void siftUpComparable(int k, T x, Object[] es) {
        Comparable<? super T> key = (Comparable<? super T>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = es[parent];
            if (key.compareTo((T) e) >= 0)
                break;
            es[k] = e;
            k = parent;
        }
        es[k] = key;
    }

我们来看一下Integer里面的源码，在Structure里面找到compare(int ,int)，因为10>5，进不来上面的循环，就可以走下面的代码，再把0下标给到5元素，从而实现小根堆。

    public int compareTo(Integer anotherInteger) {
        return compare(this.value, anotherInteger.value);
    }

    public static int compare(int x, int y) {
        return (x < y) ? -1 : ((x == y) ? 0 : 1);
    }

如果没有进入if语句，则相当于进行交换。我们如果想实现大根堆，就要走break这条语句。源码的Integer写死了，我们无法在这里进行修改，此时就需要用到比较器。

import java.util.Comparator;
import java.util.PriorityQueue;

class BigTmp implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}

public class Solution {
    public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new BigTmp());
        queue.offer(10);
        queue.offer(5);
        System.out.println(queue.peek());
    }
}

1.3. 最小K个数

第一种解法，我们可以利用冒泡排序，排完序之后，找前k个数；第二种解法，利用小根堆，找出前k个数。

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

除此之外，还有第三种解法，就是利用大根堆。先建立一个大小为k的大根堆，从数组的第k+1个元素开始遍历数组，如果数组元素比堆顶元素小，则交换，遍历结束之后，大根堆里的元素就是最小k个数。

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Solution {
    public int[] smallestK(int[] arr, int k){
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < arr.length; 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]);
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll();
        }
        return ret;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNextInt()){
            int size = in.nextInt();
            int[] arr = new int[size];
            for (int i = 0; i < size; i++) {
                arr[i] = in.nextInt();
            }
            int k = in.nextInt();
            Solution solution = new Solution();
            int[] ret = solution.smallestK(arr,k);
            System.out.println(Arrays.toString(ret));
        }
    }
}

二、堆的应用

2.1. 堆排序

如果我们要使用堆排序的思想，是采用大根堆还是小根堆呢？如果采用小根堆，那么栈顶元素就是最小的，只需要弹出依次元素即可，空间复杂度也会变大，因为还需要额外的数组来接收弹出的元素。如果采用大根堆，我们的思路是将堆顶元素与最后一个元素进行交换，再把这棵树调整为大根堆。

完整代码实现：

public class MyHeap {
    public int[] elem;
    public int usedSize;

    public MyHeap() {
        elem = new int[10];
    }

    public void Initial(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++;
            }
            if (elem[child] > elem[parent]) {
                swap(parent,child);
                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;
    }

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

public class Test {
    public static void main(String[] args) {
        int[] array = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
        MyHeap heap = new MyHeap();
        heap.Initial(array);
        heap.CreateHeap();
        heap.HeapSort();

        System.out.println();
    }
}

查看全文

http://www.kler.cn/a/576013.html