Java优先级队列解析

在看代码过程中，优先级队列(PriorityQueue)出现的次数很多，PriorityQueue是基于优先堆(完全二叉堆)的一个无界队列。

优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。每次都取最高优先权的原理是通过在内部维护一个堆来实现的。

下面先搞个小demo来感受下PriorityQueue，来个常见的面试题，求topN问题。

求topN

一组数16,7,3,20,17,8,2,1,30，求top6。
使用PriorityQueue代码如下：

public class TestPriorityQueue {
    public static void main(String[] args){
        int[] arr = {16,7,3,20,17,8,2,1,30};
        Object[] result = topN(arr, 6);
        for (int i=result.length-1; i>=0; i--) {
            System.out.println(result[i].toString());
        }
    }

    public static Object[] topN(int[] arr,int n){
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>();
        for (int i=0; i<arr.length; i++){
            if (priorityQueue.size() < n){
                priorityQueue.add(arr[i]);
            }else if (arr[i] > priorityQueue.peek()){
                priorityQueue.poll();
                priorityQueue.add(arr[i]);
            }
        }
        Object[] result = priorityQueue.toArray();
        Arrays.sort(result);
        return result;
    }
}

PriorityQueue必备知识

• 优先队列中的元素可以默认自然排序或者通过提供的Comparator在队列实例化的时排序。
• 优先队列的大小是不受限制的，但在创建时可以指定初始大小。当我们向优先队列增加元素的时候，队列大小会自动增加。
• 优先队列不允许空值，而且不支持non-comparable的对象
• 不是线程安全的。如果多个线程中的任意线程从结构上修改了queue，则这些线程不应同时访问PriorityQueue 实例，这时请使用线程安全的PriorityBlockingQueue类。
• add(offer)和poll方法提供O(log(n))时间；为remove(Object)和contains(Object)方法提供线性时间；为检索方法(peek、element和size)提供固定时间。
• 方法iterator()中提供的迭代器并不保证以有序的方式遍历优先级队列中的元素。如果需要按顺序遍历，请考虑使用 Arrays.sort(pq.toArray())。

PriorityQueue代码实现

下面代码层次解读下PriorityQueue。

首先来看下属性：

// PriorityQueue默认大小
private static final int DEFAULT_INITIAL_CAPACITY = 11;
/**
 * Priority queue represented as a balanced binary heap: the two
 * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
 * priority queue is ordered by comparator, or by the elements'
 * natural ordering, if comparator is null: For each node n in the
 * heap and each descendant d of n, n <= d.  The element with the
 * lowest value is in queue[0], assuming the queue is nonempty.
 */
// 数组来存放元素 
private transient Object[] queue;
// PriorityQueue中元素的个数
private int size = 0;
// 初始化PriorityQueue时传入比较器的接收者
private final Comparator<? super E> comparator;
// PriorityQueue被操作的次数
private transient int modCount = 0;

调用PriorityQueue的构造函数进行初始化，调用构造函数可以不传任何参数，此时用默认数组大小和默认排序方法初始化PriorityQueue，也可以传入初始化的大小或者自定义的比较器。

add 入队列

初始化之后调用add将元素放入queue中，add又调用offer，在offer中调用siftUp对元素进行调整，代码如下：

public boolean add(E e) {
    return offer(e);
}

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    // 每次操作modCount都会递增
    modCount++;
    // i是即将插入元素的索引，size是queue中元素的个数
    int i = size;
    // 达到容量上限，则调用grow扩容
    if (i >= queue.length)
        grow(i + 1);
    // queue中元素的个数更新    
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        // queue中已存在元素，则调用siftUp找到元素e在queue中的位置
        siftUp(i, e);
    return true;
}

private void siftUp(int k, E x) {
	// 根据比较策略选择不同的方法
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}        

PriorityQueue中的元素默认是按照小顶堆存放的，一个新的元素放入queue中，需要调整整个堆的顺序，PriorityQueue调用siftUp根据初始化时是否对比较器进行初始化来选择不同的调整策略，默认情况下安装对象本身的排序规则进行比较(这就要求放入PriorityQueue中的元素必须是可比较的)。

默认比较规则是siftUpComparable，代码如下：

// 参数k是queue中最后一个元素的下一个索引
private void siftUpComparable(int k, E x) {
	// 元素x实现了Comparable接口
    Comparable<? super E> key = (Comparable<? super E>) x;
    // 循环使key和k的父节点进行比较，则k只要大于0就存在父节点，
    // 小于等于0则不存在父节点，循环结束。
    while (k > 0) {
    	// root的索引是0，求出k的父节点的索引
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        // 由于queue是小顶堆，则循环跳出的条件是key比父节点大
        if (key.compareTo((E) e) >= 0)
            break;
        // key比父节点小则和父节点交换位置，继续查找
        queue[k] = e;
        k = parent;
    }
    // 将key放入合适的位置
    queue[k] = key;
}

放入新的元素对小顶堆的调整比较简单，就是假设将元素e放入queue中最后一个元素的下一个位置i，根据i找到其父节点的索引j，比较e和queue[j]的大小，如果e小，则将queue[j]从j换到i处，则j的位置就给e空了出来，然后继续循环找到j的父节点的索引，再次进行比较，直到j没有父节点，或者e小于父节点的值。

siftUpUsingComparator和siftUpComparable逻辑一样，只是两个元素进行比较时调用的方法不一样，siftUpUsingComparator调用的是对应比较器comparator.compare(x, (E) e)的方法。

grow 扩容

add元素到队列当容量满时，调用grow进行扩容，代码如下：

private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    // oldCapacity小于64则容量翻倍；否则增长50%；
    // oldCapacity是放入新元素之前的大小，翻倍的话也应该加上新元素翻倍的个数2
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // 扩容之后的容量大于MAX_ARRAY_SIZE，则将容量设为MAX_ARRAY_SIZE
    // 避免无限制的扩展
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

poll 出队列

出队列时调用poll，对queue中的size进行更新，将堆顶元素移除queue，调用siftDown进行调整。代码如下：

public E poll() {
    if (size == 0)
        return null;
    // queue中元素个数减一，也就是最后一个元素的索引
    int s = --size;
    // 操作次数递增
    modCount++;
    // 得到堆顶元素
    E result = (E) queue[0];
    // 得到queue中的最后一个元素
    E x = (E) queue[s];
    queue[s] = null;
    // queue中的元素个数不为0，则调整堆
    if (s != 0)
        siftDown(0, x);
    return result;
}

private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

siftDown的调整策略和siftUp一样也是两种，具体的调整思路是拿最后一个元素从上向下进行调整。默认调整策略的代码如下：

// 参数k始终是0，从上向下调整
private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    // 只需循环节点个数的一半
    int half = size >>> 1;        // loop while a non-leaf
    while (k < half) {
    	// root为0，k乘以2加1找到k的左孩子
        int child = (k << 1) + 1; // assume left child is least
        Object c = queue[child];
        // 右子数的索引
        int right = child + 1;
        // 在左右子树中找到较小的子树
        // 要注意right要小于size，避免越界
        if (right < size &&
            ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            // 初始假设queue[child]较小
            // 将较小值的索引赋值给child，并把元素值赋值给c
            c = queue[child = right];
        // 将最后一个元素和较小的子树c进行比较，最后一个元素小则跳出循环
        if (key.compareTo((E) c) <= 0)
            break;
        // 如果最后一个元素 比 较小的子树c大，
        // 则用较小的子树向上去填移出的父节点    
        queue[k] = c;
        k = child;
    }
    queue[k] = key;
}

siftDown时的调整思路有点绕，大致思路是堆顶元素移除之后，将最后一个元素作为指标对堆内的元素进行调整，调整时先找到左右子树的较小值，然后跟最后一个元素进行比较，子树的较小值比最后一个元素小则将较小值向上移动，否则将最后一个元素填补空缺的位置。

remove

移除queue中的指定元素，实现代码如下：

public boolean remove(Object o) {
	// 调用indexOf找到o在queue中的索引
    int i = indexOf(o);
    if (i == -1)
        return false;
    else {
    	// 移除第i个元素
        removeAt(i);
        return true;
    }
}

移除元素时先在queue中找到(顺序遍历元素，因为queue中的元素并没有顺序，则只能顺序遍历)o的索引，然后调用removeAt移除第i个元素。

indexOf的代码如下：

private int indexOf(Object o) {
    if (o != null) {
    	// for循环遍历，queue中的元素无序
        for (int i = 0; i < size; i++)
            if (o.equals(queue[i]))
                return i;
    }
    return -1;
}

调用removeAt移除第i个元素，代码如下：

private E removeAt(int i) {
    assert i >= 0 && i < size;
    modCount++;
    int s = --size;
    // 如果移除的元素是最后一个元素则直接对queue[i]赋值为null
    if (s == i) // removed last element
        queue[i] = null;
    else {
    	// 最后一个元素赋值给moved
        E moved = (E) queue[s];
        // 将最后一个元素置null，也就是清除一个元素
        queue[s] = null;
        siftDown(i, moved);
        // 如果moved比i的子树要小，将moved放在了i处，
        // 则存在moved可能比小于i的元素还要小，继续进行向上调整
        if (queue[i] == moved) {
            siftUp(i, moved);
            if (queue[i] != moved)
                return moved;
        }
    }
    return null;
}

知识扩展

Comparable和Comparator的区别

• Comparable和Comparator都是用来排序的。
• Comparable只能提供一种比较方法，Comparator可以声明不同的比较器实现多种比较方法。
• 使用Comparable时，自定义的类必须实现该接口，而Comparator则不用让自定义的类实现Comparator接口，不用对自定义的类进行任何修改。
• Comparable接口在java.lang包中，而Comparator接口在java.util包中。
• 使用Comparable时，不用在客户端进行修改，Arrays.sort()或者Collection.sort()自动调用Comparable.compareTo方法。而Comparator则需要修改，提供Comparator类，调用Comparator.compare()方法

Comparable

关于自定义的类，如果想使用Arrays或者Collections的排序方法则自定义的类可以实现Comparable接口，重写compareTo(T obj)方法，该方法的返回值可以为正数(大于)、零(等于)或者负数(小于)。

demo如下：

public class Employee implements Comparable<Employee> {

    private int id;
    private String name;
    private int age;
    private long salary;
    ... // getter setter method
    public Employee(int id, String name, int age, int salary) {
        this.id = id;
        this.name = name;
        this.age = age;
        this.salary = salary;
    }

    @Override
    public int compareTo(Employee emp) {
        //let's sort the employee based on id in ascending order
        //returns a negative integer, zero, or a positive integer as this employee id
        //is less than, equal to, or greater than the specified object.
        return (this.id - emp.id);
    }

    @Override
    //this is required to print the user friendly information about the Employee
    public String toString() {
        return "[id=" + this.id + ", name=" + this.name + ", age=" + this.age + ", salary=" +
                this.salary + "]";
    }

}

// main method
//sorting object array
Employee[] empArr = new Employee[4];
empArr[0] = new Employee(10, "Mikey", 25, 10000);
empArr[1] = new Employee(20, "Arun", 29, 20000);
empArr[2] = new Employee(5, "Lisa", 35, 5000);
empArr[3] = new Employee(1, "Pankaj", 32, 50000);

//sorting employees array using Comparable interface implementation
Arrays.sort(empArr);
System.out.println("Default Sorting of Employees list:\n"+Arrays.toString(empArr));

排序的结果如下：

Default Sorting of Employees list:
[[id=1, name=Pankaj, age=32, salary=50000], [id=5, name=Lisa, age=35, salary=5000], [id=10, name=Mikey, age=25, salary=10000], [id=20, name=Arun, age=29, salary=20000]]

使用Comparable接口可以实现自定义类的排序，但是如果排序时可能不同的需求需要根据自定义类中的不同属性进行排序，以上面的Employees为例，有人想根据salary进行排序，有人想根据age排序，此时Comparable不能实现，因为Comparable.compareTo(Object o)不能选择自定义类的属性。这里就用到了Comparator接口。

Comparator

使用Comparator接口时需要重写compare(Object o1, Object o2)方法，方法传入两个需要比较的对象，返回值可以为正数(o1大于o2)、零(等于)或者负数(小于)。

下面就来看下Employee类中不同Comparator的实现

import java.util.Comparator;

public class Employee {

    private int id;
    private String name;
    private int age;
    private long salary;
    ... // getter setter methods
    public Employee(int id, String name, int age, int salary) {
        this.id = id;
        this.name = name;
        this.age = age;
        this.salary = salary;
    }

    @Override
    //this is required to print the user friendly information about the Employee
    public String toString() {
        return "[id=" + this.id + ", name=" + this.name + ", age=" + this.age + ", salary=" +
                this.salary + "]";
    }
}

main类

import java.util.Arrays;

public class JavaObjectSorting {
// 在客户端修改
    /**
     * Comparator to sort employees list or array in order of Salary
     */
    // salary比较器
    public static Comparator<Employee> SalaryComparator = new Comparator<Employee>() {

        @Override
        public int compare(Employee e1, Employee e2) {
            return (int) (e1.getSalary() - e2.getSalary());
        }
    };

    /**
     * Comparator to sort employees list or array in order of Age
     */
    public static Comparator<Employee> AgeComparator = new Comparator<Employee>() {

        @Override
        public int compare(Employee e1, Employee e2) {
            return e1.getAge() - e2.getAge();
        }
    };

    /**
     * Comparator to sort employees list or array in order of Name
     */
    public static Comparator<Employee> NameComparator = new Comparator<Employee>() {

        @Override
        public int compare(Employee e1, Employee e2) {
            return e1.getName().compareTo(e2.getName());
        }
    };

    public static void main(String[] args) {

        //sorting custom object array
        Employee[] empArr = new Employee[4];
        empArr[0] = new Employee(10, "Mikey", 25, 10000);
        empArr[1] = new Employee(20, "Arun", 29, 20000);
        empArr[2] = new Employee(5, "Lisa", 35, 5000);
        empArr[3] = new Employee(1, "Pankaj", 32, 50000);
        
        //sort employees array using Comparator by Salary
        // 调用sort方法时，传入比较器
        Arrays.sort(empArr, JavaObjectSorting.SalaryComparator);
        System.out.println("Employees list sorted by Salary:\n"+Arrays.toString(empArr));
        
        //sort employees array using Comparator by Age
        Arrays.sort(empArr, JavaObjectSorting.AgeComparator);
        System.out.println("Employees list sorted by Age:\n"+Arrays.toString(empArr));
        
        //sort employees array using Comparator by Name
        Arrays.sort(empArr, JavaObjectSorting.NameComparator);
        System.out.println("Employees list sorted by Name:\n"+Arrays.toString(empArr));
        
    }
}

Java transient关键字

我们都知道一个对象只要实现了Serilizable接口，这个对象就可以被序列化，然而在实际开发过程中，我们常常会遇到这样的问题，这个类的有些属性需要序列化，而其他属性不需要被序列化，打个比方，如果一个用户有一些敏感信息（如密码，银行卡号等），为了安全起见，不希望在网络操作（主要涉及到序列化操作，本地序列化缓存也适用）中被传输，这些信息对应的变量就可以加上transient关键字。换句话说，这个字段的生命周期仅存于调用者的内存中而不会写到磁盘里持久化。

当对象被序列化时（写入字节序列到目标文件）时，transient阻止实例中那些用此关键字声明的变量持久化；当对象被反序列化时（从源文件读取字节序列进行重构），这样的实例变量值不会被持久化和恢复。