【深入浅出】Java 优先队列 PriorityQueue

【深入浅出】Java 优先队列 PriorityQueue

1. 基本概念

   1. PriorityQueue：优先队列，Java中优先队列保证每次取出元素的权值是队列中最小的，而CPP中是最大的。
   2. 关于该队列内部的元素大小比较，可以根据元素本身自然顺序或者使用构造函数中传入的比较器函数。
   3. PriorityQueue实现了Queue接口，但不允许空元素进入队列

2. 底层实现

   1. Java 中 PriorityQueue的底层数据结构是基于完全二叉树实现的小顶堆。
      • 完全二叉树：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部
      • 小顶堆：即按照根值<左节点值<右节点值 的规则分配元素。
   2. 用最小堆实现的特性
      • 对于节点node,它的父节点：pNode=(node-1)/2
      • 左子节点：leftNode=node*2+1
      • 右子节点：rightNode=node*2+2

3. 方法源码剖析

   1. offer()

      • offer()和add()在优先队列中有什么区别呢？区别在于返回形式，add()方法插入失败时进入异常体系处理，而offer()则是返回true/false。

      • 调整函数siftUp()：帮助小顶堆维护

      • 源码分析：

        public boolean offer(E e) {
            //小顶堆元素不能为空
            if (e == null)
                throw new NullPointerException();
            //midCount是记录该优先队列被修改的次数
            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;
        }
        
        private void siftUp(int k, E x) {
            while (k > 0) {
                //ptNo = (node-1)/2
                int parent = (k - 1) >>> 1;
                Object e = queue[parent];
                //调用比较器的比较方法，比较新加入元素和当前点的父节点值，直到当前值>parent，将元素加入，否则继续向上层比较
                if (comparator.compare(x, (E) e) >= 0)
                    break;
                queue[k] = e;
                k = parent;
                
            }
            queue[k] = x;
        }
        
        

   2. peek()

      • peek()和element()，都是使用但不取出队列首位元素，前者返回null，后者抛出异常。

      • peek()返回堆顶元素，也就是数组中最小下标的元素。

      • 源码分析

        public E peek() {
            if (size == 0)
                return null;
            return (E) queue[0];//0下标处的那个元素就是最小的那个
        }
        
        

   3. poll()

      • poll()和remove()都是获取并删除队首元素，失败时，前者返回null，后者抛出异常。

      • 调整函数： 从k指定的位置开始，将x逐层向下与当前点的左右孩子中较小的那个交换，直到x小于或等于左右孩子。

      • 源码分析

        public E poll() {
            if (size == 0)
                return null;
            int s = --size;
            modCount++;
            E result = (E) queue[0];//0下标处的那个元素就是最小的那个
            //用队列中最后一个元素占据堆顶位置，进行重新调整
            E x = (E) queue[s];
            queue[s] = null;
            if (s != 0)
                siftDown(0, x);//调整
            return result;
        }
        
        private void siftDown(int k, E x) {
            //  /2
            int half = size >>> 1;
            while (k < half) {
                int child = (k << 1) + 1;//leftNo = pNo*2+1
                Object c = queue[child];
                int right = child + 1;//rightNo = pNo*2+2
                //首先找到左右孩子中较小的那个，记录到c里，并用child记录其下标
                if (right < size &&comparator.compare((E) c, (E) queue[right]) > 0)
                   c = queue[child = right];
                
                //如果要删除的元素小于当前的左右孩子中较小者，完成
                if (comparator.compare(x, (E) c) <= 0)
                    break;
                queue[k] = c;//然后用c取代原来的值，进入堆的下一层判断
                k = child;
            }
            
            queue[k] = x;
        }
        
        

   4. remove()

   • 删除元素，如果有多个相等，只删除一个。

   • 源码分析

     //remove(Object o)
     public boolean remove(Object o) {
     	//通过遍历数组的方式找到第一个满足o.equals(queue[i])元素的下标
         int i = indexOf(o);
         if (i == -1)
             return false;
         int s = --size;
         if (s == i) //情况1.删除最后一个元素，直接卸载
             queue[i] = null;
         else {
             E moved = (E) queue[s];
             queue[s] = null;
             siftDown(i, moved);//情况2.删除其他元素，调用调整函数，重新构建小顶堆，该函数和
         }
         return true;
     }
     public E poll() {
         if (size == 0)
             return null;
         int s = --size;
         modCount++;
         E result = (E) queue[0];//0下标处的那个元素就是最小的那个
         //用队列中最后一个元素占据堆顶位置，进行重新调整
         E x = (E) queue[s];
         queue[s] = null;
         if (s != 0)
             siftDown(0, x);//调整
         return result;
     }
     
     private void siftDown(int k, E x) {
         //  /2
         int half = size >>> 1;
         while (k < half) {
             int child = (k << 1) + 1;//leftNo = pNo*2+1
             Object c = queue[child];
             int right = child + 1;//rightNo = pNo*2+2
             //首先找到左右孩子中较小的那个，记录到c里，并用child记录其下标
             if (right < size &&comparator.compare((E) c, (E) queue[right]) > 0)
                c = queue[child = right];
             
             //如果要删除的元素小于当前的左右孩子中较小者，完成
             if (comparator.compare(x, (E) c) <= 0)
                 break;
             queue[k] = c;//然后用c取代原来的值，进入堆的下一层判断
             k = child;
         }
         
         queue[k] = x;
     }