1.优先级队列介绍

1.1 优先级队列

　　有时在调度任务时，我们会想要先处理优先级更高的任务。例如，对于同一个柜台，在决定队列中下一个服务的用户时，总是倾向于优先服务VIP用户，而让普通用户等待，即使普通的用户是先加入队列的。

　　优先级队列和普通的先进先出FIFO的队列类似，最大的不同在于，优先级队列中优先级最高的元素总是最先出队的，而不是遵循先进先出的顺序。

1.2 堆

　　优先级队列的接口要求很简单。从逻辑上来说，向量、链表或者平衡二叉搜索树等数据结构都可用于实现优先级队列。但考虑到时间和空间的效率，就必须仔细斟酌和考量了。而一种被称为堆的数据结构非常适合实现优先级队列。’

　　堆和二叉搜索树类似，存储的元素在逻辑上是按照层次排放的，在全局任意地方其上层元素优先级大于下层元素，这一顺序性也被称为堆序性，而其中优先级最大的元素被放在最高的层级(大顶堆)。和二叉搜索树的排序方式不同的是，堆中元素的顺序并不是完全的排序，而只是维护了一种偏序关系，被称为堆序性。在这种偏序关系下，元素之间的顺序性比较疏散，维护堆序性的代价比较低，因而在实现优先级队列时，堆的效率要高于平衡二叉搜索树。

1.3?完全二叉堆

　　完全二叉堆是堆的一种，其元素在逻辑上是以完全二叉树的形式存放的，但实际却是存储在向量（数组）中的。在这里，我们使用完全二叉堆来实现优先级队列。

2.优先级队列ADT接口

/**
 * 优先级队列 ADT接口
 */
public interface PriorityQueue <E>{

    
     * 插入新数据
     * @param newData 新数据
     * */
    void insert(E newData);

    
     * 获得优先级最大值（窥视） 不删数据
     * @return  当前优先级最大的数据
     * */
    E peekMax();

    
     * 获得并且删除当前优先级最大值
     *   被删除的 当前优先级最大的数据
     
    E popMax();

    
     * 获得当前优先级队列 元素个数
     *  当前优先级队列 元素个数
     * int size();

    
     * 是否为空
     *  true  队列为空
     *         false 队列不为空
     * boolean isEmpty();
}

3.完全二叉堆实现细节

3.1 基础属性

　　完全二叉堆内部使用之前封装好的向量作为基础。和二叉搜索树类似，用户同样可以通过传入Comparator比较器来指定堆中优先级大小比较的逻辑。

class CompleteBinaryHeap<E> implements PriorityQueue<E>{
    
     * 内部向量
     * private ArrayList<E> innerArrayList;

    
     * 比较逻辑
     * private final Comparator<E> comparator;

    
     * 当前堆的逻辑大小
     *  size;
｝

构造方法：

 
     * 无参构造函数
     * public CompleteBinaryHeap() {
        this.innerArrayList = new ArrayList<>();
        this.comparator = null;
    }

    
     * 指定初始容量的构造函数
     *  defaultCapacity 指定的初始容量
     * public CompleteBinaryHeap( defaultCapacity){
        (defaultCapacity);
         comparator 指定的比较器逻辑
     * public CompleteBinaryHeap(Comparator<E> comparator){
        this.comparator = comparator;
    }

    
     * 指定初始容量和比较器的构造函数
     *  defaultCapacity 指定的初始容量
     * int defaultCapacity,Comparator<E> comparator) {
        
     * 将指定数组 转换为一个完全二叉堆
     *  array 指定的数组
     *  CompleteBinaryHeap(E[] array){
        (array);
        ;

        this.size = array.length;

        // 批量建堆
        heapify();
    }

     array 指定的数组
     * public CompleteBinaryHeap(E[] array,1)"> comparator;

                heapify();
    }

3.2 辅助方法

　　由于完全二叉堆在逻辑上等价于一颗完全二叉树，但实际上却采用了一维的向量数据结构来存储元素。因而我们需要实现诸如getParentIndex、getLeftChildIndex、getRightChildIndex等方法来进行完全二叉树和向量表示方法的转换。

　　这里，定义了一些私有方法来封装常用的逻辑，用以简化代码。

     * 获得逻辑上 双亲节点下标
     *  currentIndex 当前下标
     * int getParentIndex( currentIndex){
        return (currentIndex - 1)/2
     * 获得逻辑上 左孩子节点下标
     * int getLeftChildIndex(return (currentIndex * 2) + 1
     * 获得逻辑上 右孩子节点下标
     * int getRightChildIndex(return (currentIndex + 1) * 2
     * 获得末尾下标
     *  getLastIndex(){
        return this.size - 1
     * 获得最后一个非叶子节点下标
     *  getLastInternal(){
        return (this.size()/2) - 1
     * 交换向量中两个元素位置
     *  a 某一个元素的下标
     *  b 另一个元素的下标
     * void swap(int a, b){
         现暂存a、b下标元素的值
        E aData = this.innerArrayList.get(a);
        E bData = .innerArrayList.get(b);

         交换位置
        .innerArrayList.set(a,bData);
        .innerArrayList.set(b,aData);
    }

    
     * 进行比较
     * 
    @SuppressWarnings("unchecked")
     compare(E t1,E t2){
         迭代器不存在
        if(this.comparator == ){
             依赖对象本身的 Comparable，可能会转型失败
            return ((Comparable) t1).compareTo(t2);
        }else{
             通过迭代器逻辑进行比较
            .comparator.compare(t1,t2);
        }
    }

3.3 插入和上滤

　　当新元素插入完全二叉堆时，我们直接将其插入向量末尾(堆底最右侧)，此时新元素的优先级可能会大于其双亲元素甚至祖先元素，破坏了堆序性，因此我们需要对插入的新元素进行一次上滤操作，使完全二叉堆恢复堆序性。由于堆序性只和双亲和孩子节点相关，因此堆中新插入元素的非祖先元素的堆序性不会受到影响，上滤只是一个局部性的行为。

上滤操作

　　上滤的元素不断的和自己的双亲节点进行优先级的比较：

　　1. 如果上滤元素的优先级较大，则与双亲节点交换位置，继续向上比较。

　　2. 如果上滤元素的优先级较小(等于)，堆序性恢复，终止比较，结束上滤操作。

　　3. 特别的，当上滤的元素被交换到树根节点时(向量下标第0位)，此时由于上滤的元素是堆中的最大元素，终止上滤操作。

上滤操作的时间复杂度：

（编辑：衡阳站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!