对象的比较（上）PriorityQueue中的底层源码解析

作者：~小明学编程 

文章专栏：Java数据结构

格言：目之所及皆为回忆，心之所想皆为过往

目录

问题引入

offer()

扩容

构造方法

grow()

siftUp()

siftUpComparable（）

---

问题引入

问题是这样的，我们现在有一个类，这个类是一个扑克牌的类，类里面有我们的花色和数字，现在我们有一个优先级的队列，我们向队列里面offer()元素，这时问题就来了，我们怎么才能让我们堆里面的对象按照我们想要的方式进行排序呢？

class Card{
    public int rank; // 数值
    public String suit; // 花色
    public Card(int rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }
 
    @Override
    public String toString() {
        return "Card{" +
                "rank=" + rank +
                ", suit='" + suit + '\'' +
                '}';
    }
}
 
public class Test {
    public static void main(String[] args) {
        //默认是一个小堆
        PriorityQueue priorityQueue = new PriorityQueue<>();
        Card card1 = new Card(2,"♠");
        Card card2 = new Card(3,"♠");
        priorityQueue.offer(new Card(5,"♥"));
        priorityQueue.offer(new Card(2,"♠"));
        System.out.println(priorityQueue);
//        System.out.println(card1.compareTo(card2));
    }
}

只是我们最开始的代码，我们打算向我们的堆里面放入我们的card。

 然后当我们运行代码的时候，发现会报错，具体因为啥下面详细说，现在我们要明白的是，既然想向我们的堆里面放东西你总得有个顺序，所以我们这里要写一个比较方法，这个时候就需要我们实现 Comparable接口然后重写我们的 compareTo 方法。

class Card implements Comparable{
    public int rank; // 数值
    public String suit; // 花色
    public Card(int rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }
 
    @Override
    public int compareTo(Card o) {
        return this.rank - o.rank;
    }
 
    @Override
    public String toString() {
        return "Card{" +
                "rank=" + rank +
                ", suit='" + suit + '\'' +
                '}';
    }
}

 可以看到这里我们就实现了从小到大的排序，那么这个过程是怎么实现的呢？

offer()

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

这就是我们的源码，我们可以看到，类型的话是一个泛型，e是我们当前传进去的对象，首先会有一个判断，如果e为空那么就直接抛出一个异常。

扩容

 接下来就是一个判断当前数组元素个数并且考虑是否需要扩容的问题了，当我们的i>=queue.length的时候就需要grow()了，所以现在我们需要知道这个数组的初始值是多大。

构造方法

 当我们创建对象的时候我们是没给对象传参数的，所以我们将会调用我们的无参构造方法，然后通过this（）传了两个参数，调用我们带两个参数的构造方法，再下面就是new了一个Object[]类型的数组，数组的大小是 DEFAULT_INITIAL_CAPACITY = 11 ，comparator是null。

grow()

    private void grow(int minCapacity) {
        int oldCapacity = queue.length;
        // Double size if small; else grow by 50%
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));
        // overflow-conscious code
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        queue = Arrays.copyOf(queue, newCapacity);
    }

这里的源码很容易理解，首先确定一下旧的数组大小也就是oldCapacity，我们新的大小为：

如果我们旧的数组的大小小于64，新的数组的大小就为2*oldCapacity+2，反之新数组的大小就为1.5*oldCapacity。

完成扩容时候就该往数组里放元素了。

 当我们是第一次向里面放元素时，也就是i==0，queue[0] = e。

当我们不是第一个元素的时候，例如我们放第二个元素，此时的i==1,我们进入siftUp()。

siftUp()

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

在我们进入shfiUp()之后，会进行一个判断，因为我们的comparator是null，所以我们继续调用

siftUpComparable(k, x) 这个方法，

siftUpComparable（）

    private void siftUpComparable(int k, E x) {
        Comparablesuper E> key = (Comparablesuper E>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }

源码的大致思路是这样的，k为我们添加元素的个数-1，也就是数组的下标，找到我们的双亲节点

 key就是我们当前传进去的x，然后  key.compareTo((E) e)  因为我们重写了compareTo，所以这里直接接受 this.rank - o.rank 的返回值，也就是e2.rank - e1.rank此时等于-3<0，所以向下执行，

queue[k] = e

 k = parent  然后我们的k==0退出循环

queue[k] = key