PriorityQueue源码解析

出来看星星吗？不看星星出来也行。 / 2024-08-23 / 原文

PriorityQueue

优先级队列：默认每次取出权值最小的元素，元素的大小评判可以通过元素自身的自然顺序，也可以在构造时传入比较器进行定义顺序规则。

用法

//不传比较器
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(3);
pq.add(4);
pq.add(1);
pq.add(2);
//输出顺序 1 2 3 4
//使用比较器
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b-a);
pq.add(3);
pq.add(4);
pq.add(1);
pq.add(2);
//输出顺序 4 3 2 1

概述

底层通过堆实现，具体是使用完全二叉树实现的小顶堆。所以可以通过数组来作为底层实现

对于任意一个下标i，在不溢出的前提下

lson = i * 2 + 1
rson = i * 2 + 2
parent = (i-1) / 2

时间复杂度

由于使用了堆这种数据结构，在添加元素和删除元素时需要调整堆，所以添加删除操作的时间复杂度都是O(longN)，peek和element方法是常数时间。

插入的时候插入队尾，然后调整堆

删除操作的时候将堆顶和队尾元素交换，然后删除队尾，然后调整堆

堆排序源码

堆排序其实就两个操作，首先是建堆，其次是排序

    private void heapSort(int[] nums, int n) {
        //建堆
        for(int i = (n-1) / 2; i >=0; i--){
            heapify(nums, n, i);
        }
        //排序
        for(int i = n - 1; i >= 0; i--){
            swap(nums, 0, i);
            heapify(nums, i, 0);
        }

    }

    private void heapify(int[] nums, int n, int i) {
        int largest = i;
        int lson = i*2+1;
        int rson = i*2+2;
        if(lson < n && nums[lson] > nums[largest]){
            largest = lson;
        }
        if(rson < n && nums[rson] > nums[largest]){
            largest = rson;
        }
        if(largest!=i) {
            swap(nums, i, largest);
            heapify(nums, n, largest);
        }
    }