优先队列

队列的数据结构我们都熟悉，先进先出,后进后出的数据结构，当我们提交若干个下载任务给某网盘，进行批量下载，所有的任务会被加入一个下载队列。在批量下载过程中下载器需要优秀下载耗时较短的任务，这样会加快整个下载任务的进度。显然这样的场景在现代计算机当中很常见，这种特殊的队列就是优先队列。在上面的例子中耗时短就是优先权。

实现优先队列有很多种方式常见的有有序单链表的形式，头节点最小，但是插入的就比较费劲，需要时刻维护单链表的有序性。还有就是使用二叉查找树，这样以来最小的永远是左子树的左节点。不过当左子树一直删除之后就会退化为单链表。这样的实现起来操作莫名的复杂，而起退货的

二叉堆（完全二叉树）

为了简化上述的复杂操作，优先队列使用二叉堆来实现，二叉堆呢是一颗完全，完全二叉树一颗高度为H的完全二叉树有$2^{h$节点或者$2}{k+1} - 1$个节点，那么该树的高度就是$logN$,显然用完全二叉树做优先队列的时间复杂度就是$O(log_N)$
binaryTree

结构特性

arrayStore
二叉堆完全可以使用数组来存放，对于数组任意一个位置的元素$i$,，其左儿子在$2i$上,右儿子在$(2i+1)$,而其父节点在$[i/2]$上

堆序特性

看了上面的数组表示的堆按照字典顺序来看最小元素在根节点处，获取堆顶元素，只需获取根节点即可。可以确定是，除根节点之外，在小顶堆中任意一个节点Q,会小于他的任意一个后裔。所有堆中的元素需要实现比较器

@ToString
public class MoodBinnaryHeap<T extends Comparable<? super T>> {

    public volatile Object[] arrays;

    private final AtomicInteger currentSize = new AtomicInteger(0);

    private final Integer DEFAYULT_CAPACITY = 10;

    public MoodBinnaryHeap() {
        arrays = new Object[DEFAYULT_CAPACITY];
    }

    public MoodBinnaryHeap(int capacity) {
        arrays = new Object[capacity < 0 ? DEFAYULT_CAPACITY : capacity];
    }
}

堆的基操-插入

无论是大顶堆还是小订堆，在插入之后都需要去维护堆序。在堆中插入一个元素。需要先找到可插入的位置，判断插入当前元素之后堆序是否发升变化，即判断要插入节点的父节点和该元素比较是否满足堆序。满足条件直接插入就完事，不满足则需要在要进行插入的节点放一个空节点。然后交换空节点和父节点，让空节点和父节点交换位置,一直重复这个过程，直到要插入的元素可以方式空节点为止。

/**
     * 扩容
     */
    private void enlargeArray() {
        Object[] newArrays = new Object[(arrays.length << 1)+1];
        System.arraycopy(arrays, 0, newArrays, 0, arrays.length);
        arrays = newArrays;
    }

    /**
     * 插入
     *
     * @param t
     */
    public void offer(T t) {
        if (currentSize.get() == arrays.length - 1) {
            enlargeArray();
        }
        int hole = currentSize.incrementAndGet();
        for (arrays[0] = t; t.compareTo((T) arrays[hole / 2]) < 0; hole /= 2) {
            arrays[hole] = arrays[hole / 2];
        }
        arrays[hole] = t;
        arrays[0] = null;
    }

此时老哥你是否了解了arrays[0]的涵义了，这种策略就叫做上滤

堆的基操-删除最小元素

删除堆顶元素和插入类似，当需要删除堆顶元素时，先把根节点设置为空，应为要删除一个元素，所以堆的最后一个节点必然会出现在一个新的位置，那么让最后一个节点可以放在原来根节点，而起还满足堆序，那就删除成功，反之需要把最后一个节点从根出发的最小节点路径上找一个合适的位置。就是把空节点一直往下移动。这个过程叫做下滤

  public T peek() {
        if (currentSize.get()==0){
            throw  new RuntimeException();
        }
        T minitem=findMin();
        arrays[1]=arrays[currentSize.getAndDecrement()];
        precolateDown(1);
        return minitem;
    }

    private T findMin() {
        return (T) arrays[1];
    }


    private void precolateDown(int hole) {
        int child=0;
        T temp = (T) arrays[hole];

        for (; hole * 2 <= currentSize.get(); hole = child) {
            child = hole * 2;
            if (child != currentSize.get() && ((T) (arrays[child + 1])).compareTo(((T) (arrays[child]))) < 0) {
                child++;
            }
            if (((T) (arrays[child])).compareTo(temp) < 0) {
                arrays[hole] = arrays[child];
            } else {
                break;
            }
        }
        System.out.println(child);
        arrays[hole] = temp;
    }

优先队列的应用

选择问题

经典算法查找一个无序数组中的第 K 大(小)元素。

Java中的优先队列默认是小顶堆，维护K个容量的小顶堆的堆顶元素就是数组中第K个大的元素
   public int findKMax(int[] nums,int k){
        PriorityQueue<Integer> priorityQueue=new PriorityQueue();
        for(int i=0;i<nums.length;i++){
            priorityQueue.offer(nums[i]);
            if (priorityQueue.size()>k){
                priorityQueue.poll();
            }
        }
        return priorityQueue.peek();
    }

使用我们自定义的二叉堆来实现这个算法

 public T findKMax(int[] nums,int k){
        MoodBinnaryHeap moodBinnaryHeap=new MoodBinnaryHeap();
        for (int i=0;i<nums.length;i++){
            moodBinnaryHeap.offer(nums[i]);
            if (moodBinnaryHeap.size()>k){
                moodBinnaryHeap.poll();
            }
        }
        return (T) moodBinnaryHeap.peek();
    }