JAVA集合排序算法之PriorityQueue堆排序

如PriorityQueue堆排序

• 完全二叉树
• 堆中任一节点大于等于（大顶堆）（或小于等于（小顶堆））左右子节点

数组 可便捷的处理堆结构

如上图的堆用长度为9的数组表示，int[] heapArray = new int[9]
堆顶元素数组索引0，即heapArray[0]
给定索引 i，则左子节点索引：left = (i << 1) + 1，右子节点索引：right = left + 1，父节点索引：i >>> 1

PrioritQueue为小顶堆，即任一节点元素小于等于左右子节点，JDK源码定义部分：

    
    private transient Object[] queue;

    
    private int size = 0;

    
    private final Comparator comparator;

• Object[] queue – 数组存储
• size – 队列长度

插入元素：

    
    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;
        //数组长度为0，即第1个元素直接存储到数组[]位置0
        if (i == 0)
            queue[0] = e;
        else
        //队列多于1个元素时，插入元素需进行堆化处理
            siftUp(i, e);
        return true;
    }

堆化：插入元素后仍然符合堆的特性

private void siftUp(int k, E x) {
        //如果指定了比较器Comparator，基于指定Comparator堆化，
        //如果未指定Comparator，基于元素自然顺序，即元素E需实现Comparator
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }

    //自底向上堆化
    private void siftUpComparable(int k, E x) {
        Comparable key = (Comparable) x;
        while (k > 0) {
            //父节点索引
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            //新插入元素与父节点比较
            //若新插入元素大于等于父节点元素，则直接插入当前位置 k
            //否则，继续与父节点比较
            if (key.compareTo((E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        //插入新元素
        queue[k] = key;
    }

堆化示意图：