一 什么是优先队列？

1⃣️ 优先队列其实就是队列的一种，不过优先队列是区别于普通队列的；普通队列是一种先进先出，后进后出的数据结构，优先队列和普通队列的区别就在于，出队的顺序和入队的顺序无关，是和优先级息息相关的；

优先队列的使用场景1

在这个场景中，由于现在计算机都是多任务执行的，我们的操作系统会动态的选择优先级最高的任务执行；因为我们无法准确预估有多少的任务需要处理，所以我们我们的操作系统只能根据优先级来进行资源的分配；

2⃣️ 优先队列的底层实现方式：

优先队列的实现方式

普通线性结构(数组 链表)：入队其实就是一个添加的操作，所以时间复杂度为O(1);但是出队的操作由于需要执行查询的操作所以时间复杂度是O(n)的；
顺序线性结构：与普通线性结构相比，不对的操作是O(1)的，但是入队是O(n)的，因为在入队的时候我们需要对新插入的元素进行比较以便于确定新插入元素的位置；
堆：堆是一种高效的数据结构，用堆来实现优先队列的话它的入队和出队时间复杂度都是O(logn)的级别，这里说的O(logn)是指在最坏的情况下都是这个级别的。

二 堆的基本表示

二叉堆图示

说白了，二叉堆就是满足一些特殊性质的二叉树；

1⃣️ 二叉堆的特殊性质

1. 首先二叉堆是一颗完全二叉树；
   二叉堆特性1
   上图是一个满二叉树，在介绍二分搜索树的笔记里有关于满二叉树的介绍：满二叉树表示出了叶子节点，其他的各个节点都有左右两个节点；但是满二叉树并不是完全二叉树
   完全二叉树图示
   完全二叉树：把元素数据排列成树的形状就是完全二叉树；所以对于完全二叉树来说，树的右下角可能会有缺失甚至是空的；

2.在堆中某个节点的值总是不大于其父节点的值；

最大堆图示

注意：从图中可以看到二叉堆中的某些节点甚至小于叶子节点的值，但是这并不影响二叉堆的特性，在二叉堆中节点的值和节点所处的层次之间是没有关系的。

只有同时满足了以上两个特性才能称为二叉堆；

2⃣️ 二叉堆的实现方式

1. 我们完全可以使用实现二分搜索树的方式来实现二叉堆，但是由于二叉堆是通过把元素数据按照顺序进行排列形成的树的形状，所以我们可以使用数组的方式来实现二叉堆
   二叉堆的实现图示

   通过这个图我们可以清楚的看到二叉堆中的各个元素的层级顺序是怎样的，所有我们可以直接使用数组来实现这样的一个结构；

2. 当我们使用数组来实现这样一个结构的时候我们怎么去表示一个节点的左右子节点呢？如果我们使用二分搜索树那样的实现方式来实现的话，我们可以通过定义节点的左右子节点来实现，但是在数组中我们显然不能使用节点定义这样的方式；但是通过观察我们发现了这样的一个规律，就是对于任意个节点来说，它的左节点的索引是其父节点索引的2倍，右节点是其父节点索引的2倍+1；
   left child(i) = 2 * I;
   right child(i) = 2 * i + 1;
   使用这样的方式还有一个好处就是，我们可以很容易的通过任意一个节点找到其父节点，可以直接使用当前节点除以2就可以找到父节点，如果是右节点的话是需要取整的也就是说需要将小数部分抹除掉；
   parent(i) = i / 2;
   这就是使用数组来实现二叉堆的好处，数组的索引之间是存在这样的逻辑关系的；

3. 当我们使用数组来实现这样的结构时还有一个问题，就是数组中索引为0的位置该怎么处理？之前在实现循环队列以及链表的时候我们会有意的浪费一个节点，但是在这里我们不用采用这样的方式，我们只需要对我们的节点进行一次偏移的操作就可以了
   parent(i) = (i - 1) / 2;
   left child(i) = 2 * i + 1;
   right child(i) = 2 * i + 2;
   这样我们就可以直接使用这个索引为0的位置了；

三 代码实现最大二叉堆

package com.mufeng.MaxHeap;

import com.mufeng.arrays.Array;

/**
 * Created by wb-yxk397023 on 2018/7/7.
 */
public class MaxHeap<E extends Comparable<E>> {

    private Array<E> data;

    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }

    public MaxHeap(){
        data = new Array<>();
    }

    /**
     * 返回堆中的元素个数
     * @return
     */
    public int getSize(){
        return data.getSize();
    }

    /**
     * 返回一个boolean值，表示堆是否为空
     * @return
     */
    public boolean isEmpty(){
        return data.isEmpty();
    }

    /**
     * 返回完全二叉树的数组表示中，一个索引的父节点索引值
     * @param index
     * @return
     */
    private int parent(int index){
        if (index == 0){
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        }
        return (index - 1) / 2;
    }

    /**
     * 返回完全二叉树的数组表示中，一个父节点的左节点的索引值
     * @param index
     * @return
     */
    private int leftChild(int index){
        return index * 2 + 1;
    }

    /**
     * 返回完全二叉树的数组表示中，一个父节点的右节点的索引值
     * @param index
     * @return
     */
    private int rightChild(int index){
        return index * 2 + 2;
    }
}

四 向堆中添加元素和Sift Up

1⃣️ 添加过程图示

向堆中添加一个元素1

从树型结构的角度去看，添加一个元素等于是在树中增加一个节点，但是我们的二叉堆底层是使用数组实现的，所以向堆中添加元素实际上操作的是数组

向堆中添加一个元素2

从这张图片可以看出，添加一个元素就相当于在索引为10的位置插入一个元素，但是这样的操作虽然说满足了完全二叉树的结构，但是并没有满足某个节点的值总是不大于其父节点的值这个特性，所以我们还需要进行调整

向堆中添加元素3

调整也是比较简单的，因为就算是出现需要调整的情况也是发生在新加入的元素与其父节点以及祖先节点的这条链路上，所以我们只要对这一条链路进行调整即可；

向堆中添加元素4

所以在这里我们将新加入的数据以及对应的父节点进行比较，然后进行位置的对调即可；

向堆中添加元素5

调整完毕以后我们发现还是不能完全满足二叉堆的特性，所以我们继续重复上一步操作进行元素位置的对调；

向堆中添加元素6

到这里堆中元素的调整过程就完成了，

向堆中添加元素7

这个过程就是Sift Up也就是堆中元素的上浮过程；

2⃣️ 代码实现

    /**
     * 向堆中添加一个元素
     * @param e
     */
    public void add(E e){
        data.addLast(e);
        // 执行siftUp操作
        siftUp(data.getSize() - 1);
    }

    /**
     * 元素上浮操作
     * @param k
     */
    private void siftUp(int k){
        while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0){
            data.swap(k, parent(k));
            k = parent(k);
        }
    }
}

/**
     * 元素位置交换
     * @param I
     * @param j
     */
    public void swap(int i, int j){
        if (i < 0 || i >= size || j < 0 || j >= size){
            throw new IllegalArgumentException("Index is illegal.");
        }
        E t = data[I];
        data[i] = data[j];
        data[j] = t;
    }

五 从堆中取出元素和Sift Down

1⃣️ 从堆中取出元素图示

从堆中取出元素1

由于我们的二叉堆是一个最大二叉堆，所以我们的取出操作只能取出最大的那个值，也就是索引为0的值，

从堆中取出元素2

但是取出的最大值同时也是堆中的根节点一旦取出就会导致二叉堆结构的不成立，所以我们需要想办法解决这个问题，第一种方式是将剩下的两个堆融合在一起，但是这样做的话会非常麻烦；所以我们采用其他方法来解决这个问题；

从堆中取出元素3

如图所示，我们采用的方式是将最后一个值放到被取出值的位置；这样的话我们的二叉堆的根节点就变成了16，然后我们删除最后一个节点

从堆中取出元素4

这样我们的数组中就没有索引为10的元素了，从元素个数的角度看本次操作是成功的，但是这样操作以后我们的二叉堆的特性就得不到满足了，

从堆中取出元素5

这个时候我们就将根节点与其对应的左右子节点进行对比，如果根节点小于左右根节点我们就将根节点与两个子节点中最大的那个进行位置的交换；

从堆中取出元素6

在本次示例我们将16与52进行位置上的交换；交换完成以后52这个元素作为根节点就比它的两个子节点都大了；

从堆中取出元素7

由于交换完成以后有可能会出现无法满足二叉堆特性的情况所以仍要继续进行交换；

从堆中取出元素8

交换完成以后的节点很明显比其子节点要大

从堆中取出元素9

然后我们在将16与其子节点进行对比，由于这一次子节点只有一个我们只能对比一个，对比以后发现子节点是小于它的父节点，同时也是满足二叉堆的特性的就不进行位置上的交换了；这个过程就叫做Sift Down(数据下沉)，通过这个操作我们就完成从堆中取出一个数据的操作。

2⃣️ 代码实现

/**
     * 查看堆中的最大元素
     * @return
     */
    public E findMax(){
        if (data.getSize() == 0){
            throw new IllegalArgumentException("Can not findMax when heap is empty.");
        }
        return data.get(0);
    }

    /**
     * 从堆中取出最大的元素
     * @return
     */
    public E extractMax(){
        E ret = findMax();
        data.swap(0,data.getSize() - 1);
        data.removeLast();
        siftDown(0);
        return ret;
    }

    /**
     * 元素下沉
     * @param k
     */
    private void siftDown(int k){
        while (leftChild(k) < data.getSize()){
            int j = leftChild(k);

            if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0){
                j = rightChild(k);
            }

            if (data.get(k).compareTo(data.get(k)) >= 0){
                break;
            }
            
            data.swap(k, j);
            k = j;
        }
    }

3⃣️ 测试

public static void main(String[] args) {

        int n = 1000000;

        MaxHeap<Integer> maxHeap = new MaxHeap<>();
        Random random = new Random();
        for(int i = 0 ; i < n ; i ++)
            maxHeap.add(random.nextInt(Integer.MAX_VALUE));

        int[] arr = new int[n];
        for(int i = 0 ; i < n ; i ++)
            arr[i] = maxHeap.extractMax();

        for(int i = 1 ; i < n ; i ++)
            if(arr[i-1] < arr[i])
                throw new IllegalArgumentException("Error");

        System.out.println("Test MaxHeap completed.");
    }

测试结果

六 Heapify和Replace

1⃣️ Replace

1. 什么是Replace
   取出最大元素后，放入一个新元素。

2.怎么实现？
可以先执行extractMax操作，在进行一次add操作来实现，但是这样的效果不是很好，因为这样的话需要执行两次O(logn)的操作；所以我们使用其他的实现方式：可以将堆顶的元素替换以后Sift Down，这样的话我们只需要执行一次O(logn)操作；

/**
     * 取出堆中的最大元素，并替换成元素e
     * @param e
     * @return
     */
    public E replace(E e){
        E ret = findMax();

        data.set(0, e);
        siftDown(0);

        return ret;
    }

2⃣️ Heapify

1.什么是Replace
将任意数组整理成堆的形状；

2.怎么实现？
遍历一下数组，然后将数组中的元素按照二叉堆的特性进行排序即可，但是由于这样做效率会比较低这里并不推荐；

3.更高效的实现。

Heapify图示1

如图所示这是一个完全二叉树，但是并不满足二叉堆的特性；

Heapify图示2

所以我们根据上图中的二叉树找到倒数第一个非叶子节点，然后对这个节点按照倒叙从后往前不断的进行Sift Down的操作就可以了；但是这里有一个问题就是我们怎么确定倒数第一个非叶子节点的索引是多少呢？我们可以从最后一个节点的位置计算出最后一个非叶子节点的索引；实现过程请参考图示：

Heapify图示3

Heapify图示4

Heapify图示5

Heapify图示6

Heapify图示7

Heapify图示8

Heapify图示9

Heapify图示10

至此我们的Heapify的操作就完成了；

4. 代码实现

/**
     * 构造函数，入参为数组
     * @param arr
     */
    public Array(E[] arr){
        data = (E[]) new Object[arr.length];
        for (int i = 0; i < arr.length; i++){
            data[i] = arr[i];
        }
        size = arr.length;
    }

/**
     * Heapify
     * @param arr
     */
    public MaxHeap(E[] arr){
        data = new Array<>(arr);
        for (int i = parent(arr.length - 1); i >= 0; i--){
            siftDown(i);
        }
    }

5. 测试

public class Main {

    private static double testHeap(Integer[] testData, boolean isHeapify){

        long startTime = System.nanoTime();

        MaxHeap<Integer> maxHeap;
        if(isHeapify)
            maxHeap = new MaxHeap<>(testData);
        else{
            maxHeap = new MaxHeap<>();
            for(int num: testData)
                maxHeap.add(num);
        }

        int[] arr = new int[testData.length];
        for(int i = 0 ; i < testData.length ; i ++)
            arr[i] = maxHeap.extractMax();

        for(int i = 1 ; i < testData.length ; i ++)
            if(arr[i-1] < arr[i])
                throw new IllegalArgumentException("Error");
        System.out.println("Test MaxHeap completed.");

        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }

    public static void main(String[] args) {

        int n = 1000000;

        Random random = new Random();
        Integer[] testData = new Integer[n];
        for(int i = 0 ; i < n ; i ++)
            testData[i] = random.nextInt(Integer.MAX_VALUE);

        double time1 = testHeap(testData, false);
        System.out.println("Without heapify: " + time1 + " s");

        double time2 = testHeap(testData, true);
        System.out.println("With heapify: " + time2 + " s");
    }
}

测试结果

七 基于堆的优先队列

1⃣️ 实现优先队列接口

package com.mufeng.MaxHeap;

/**
 * Created by wb-yxk397023 on 2018/6/9.
 */
public interface Queues<E> {

    /**
     * 获取队列中元素的个数
     * @return
     */
    int getSize();

    /**
     * 判断队列中是否是空的
     * @return
     */
    boolean isEmpty();

    /**
     * 向队列中添加一个元素(入队)
     * @param e
     */
    void enqueues(E e);

    /**
     * 从队列中删除一个元素(出队)
     * @return
     */
    E dequeues();

    /**
     * 获取对首的元素
     * @return
     */
    E getFront();
}

2⃣️ 实现优先队列类

package com.mufeng.MaxHeap;

/**
 * Created by wb-yxk397023 on 2018/7/7.
 */
public class PriorityQueues<E extends Comparable<E>> implements Queues<E> {

    /**
     * 引入MaxHeap
     */
    private MaxHeap<E> maxHeap;

    /**
     * 构造器
     */
    public PriorityQueues(){
        maxHeap = new MaxHeap<>();
    }

    
    @Override
    public int getSize() {
        return maxHeap.getSize();
    }

    @Override
    public boolean isEmpty() {
        return maxHeap.isEmpty();
    }

    @Override
    public void enqueues(E e) {
        maxHeap.add(e);
    }

    @Override
    public E dequeues() {
        return maxHeap.extractMax();
    }

    @Override
    public E getFront() {
        return maxHeap.findMax();
    }
}

八 练习

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
例如，
给定数组 [1,1,1,2,2,3] , 和 k = 2，返回 [1,2]。
注意：你可以假设给定的 k 总是合理的，1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

package com.mufeng.MaxHeap;

/**
 * Created by wb-yxk397023 on 2018/7/7.
 */
import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;

class Solution {

    private class Array<E> {

        private E[] data;
        private int size;

        // 构造函数，传入数组的容量capacity构造Array
        public Array(int capacity){
            data = (E[])new Object[capacity];
            size = 0;
        }

        // 无参数的构造函数，默认数组的容量capacity=10
        public Array(){
            this(10);
        }

        public Array(E[] arr){
            data = (E[])new Object[arr.length];
            for(int i = 0 ; i < arr.length ; i ++)
                data[i] = arr[i];
            size = arr.length;
        }

        // 获取数组的容量
        public int getCapacity(){
            return data.length;
        }

        // 获取数组中的元素个数
        public int getSize(){
            return size;
        }

        // 返回数组是否为空
        public boolean isEmpty(){
            return size == 0;
        }

        // 在index索引的位置插入一个新元素e
        public void add(int index, E e){

            if(index < 0 || index > size)
                throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");

            if(size == data.length)
                resize(2 * data.length);

            for(int i = size - 1; i >= index ; i --)
                data[i + 1] = data[i];

            data[index] = e;

            size ++;
        }

        // 向所有元素后添加一个新元素
        public void addLast(E e){
            add(size, e);
        }

        // 在所有元素前添加一个新元素
        public void addFirst(E e){
            add(0, e);
        }

        // 获取index索引位置的元素
        public E get(int index){
            if(index < 0 || index >= size)
                throw new IllegalArgumentException("Get failed. Index is illegal.");
            return data[index];
        }

        // 修改index索引位置的元素为e
        public void set(int index, E e){
            if(index < 0 || index >= size)
                throw new IllegalArgumentException("Set failed. Index is illegal.");
            data[index] = e;
        }

        // 查找数组中是否有元素e
        public boolean contains(E e){
            for(int i = 0 ; i < size ; i ++){
                if(data[i].equals(e))
                    return true;
            }
            return false;
        }

        // 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
        public int find(E e){
            for(int i = 0 ; i < size ; i ++){
                if(data[i].equals(e))
                    return i;
            }
            return -1;
        }

        // 从数组中删除index位置的元素, 返回删除的元素
        public E remove(int index){
            if(index < 0 || index >= size)
                throw new IllegalArgumentException("Remove failed. Index is illegal.");

            E ret = data[index];
            for(int i = index + 1 ; i < size ; i ++)
                data[i - 1] = data[i];
            size --;
            data[size] = null; // loitering objects != memory leak

            if(size == data.length / 4 && data.length / 2 != 0)
                resize(data.length / 2);
            return ret;
        }

        // 从数组中删除第一个元素, 返回删除的元素
        public E removeFirst(){
            return remove(0);
        }

        // 从数组中删除最后一个元素, 返回删除的元素
        public E removeLast(){
            return remove(size - 1);
        }

        // 从数组中删除元素e
        public void removeElement(E e){
            int index = find(e);
            if(index != -1)
                remove(index);
        }

        public void swap(int i, int j){

            if(i < 0 || i >= size || j < 0 || j >= size)
                throw new IllegalArgumentException("Index is illegal.");

            E t = data[i];
            data[i] = data[j];
            data[j] = t;
        }

        @Override
        public String toString(){

            StringBuilder res = new StringBuilder();
            res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
            res.append('[');
            for(int i = 0 ; i < size ; i ++){
                res.append(data[i]);
                if(i != size - 1)
                    res.append(", ");
            }
            res.append(']');
            return res.toString();
        }

        // 将数组空间的容量变成newCapacity大小
        private void resize(int newCapacity){

            E[] newData = (E[])new Object[newCapacity];
            for(int i = 0 ; i < size ; i ++)
                newData[i] = data[i];
            data = newData;
        }
    }

    private class MaxHeap<E extends Comparable<E>> {

        private Array<E> data;

        public MaxHeap(int capacity){
            data = new Array<>(capacity);
        }

        public MaxHeap(){
            data = new Array<>();
        }

        public MaxHeap(E[] arr){
            data = new Array<>(arr);
            for(int i = parent(arr.length - 1) ; i >= 0 ; i --)
                siftDown(i);
        }

        // 返回堆中的元素个数
        public int size(){
            return data.getSize();
        }

        // 返回一个布尔值, 表示堆中是否为空
        public boolean isEmpty(){
            return data.isEmpty();
        }

        // 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
        private int parent(int index){
            if(index == 0)
                throw new IllegalArgumentException("index-0 doesn't have parent.");
            return (index - 1) / 2;
        }

        // 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
        private int leftChild(int index){
            return index * 2 + 1;
        }

        // 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
        private int rightChild(int index){
            return index * 2 + 2;
        }

        // 向堆中添加元素
        public void add(E e){
            data.addLast(e);
            siftUp(data.getSize() - 1);
        }

        private void siftUp(int k){

            while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0 ){
                data.swap(k, parent(k));
                k = parent(k);
            }
        }

        // 看堆中的最大元素
        public E findMax(){
            if(data.getSize() == 0)
                throw new IllegalArgumentException("Can not findMax when heap is empty.");
            return data.get(0);
        }

        // 取出堆中最大元素
        public E extractMax(){

            E ret = findMax();

            data.swap(0, data.getSize() - 1);
            data.removeLast();
            siftDown(0);

            return ret;
        }

        private void siftDown(int k){

            while(leftChild(k) < data.getSize()){
                int j = leftChild(k); // 在此轮循环中,data[k]和data[j]交换位置
                if( j + 1 < data.getSize() &&
                        data.get(j + 1).compareTo(data.get(j)) > 0 )
                    j ++;
                // data[j] 是 leftChild 和 rightChild 中的最大值

                if(data.get(k).compareTo(data.get(j)) >= 0 )
                    break;

                data.swap(k, j);
                k = j;
            }
        }

        // 取出堆中的最大元素，并且替换成元素e
        public E replace(E e){

            E ret = findMax();
            data.set(0, e);
            siftDown(0);
            return ret;
        }
    }

    private interface Queue<E> {

        int getSize();
        boolean isEmpty();
        void enqueue(E e);
        E dequeue();
        E getFront();
    }

    private class PriorityQueue<E extends Comparable<E>> implements Queue<E> {

        private MaxHeap<E> maxHeap;

        public PriorityQueue(){
            maxHeap = new MaxHeap<>();
        }

        @Override
        public int getSize(){
            return maxHeap.size();
        }

        @Override
        public boolean isEmpty(){
            return maxHeap.isEmpty();
        }

        @Override
        public E getFront(){
            return maxHeap.findMax();
        }

        @Override
        public void enqueue(E e){
            maxHeap.add(e);
        }

        @Override
        public E dequeue(){
            return maxHeap.extractMax();
        }
    }

    private class Freq implements Comparable<Freq>{

        public int e, freq;

        public Freq(int e, int freq){
            this.e = e;
            this.freq = freq;
        }

        @Override
        public int compareTo(Freq another){
            if(this.freq < another.freq)
                return 1;
            else if(this.freq > another.freq)
                return -1;
            else
                return 0;
        }
    }

    public List<Integer> topKFrequent(int[] nums, int k) {

        TreeMap<Integer, Integer> map = new TreeMap<>();
        for(int num: nums){
            if(map.containsKey(num))
                map.put(num, map.get(num) + 1);
            else
                map.put(num, 1);
        }

        PriorityQueue<Freq> pq = new PriorityQueue<>();
        for(int key: map.keySet()){
            if(pq.getSize() < k)
                pq.enqueue(new Freq(key, map.get(key)));
            else if(map.get(key) > pq.getFront().freq){
                pq.dequeue();
                pq.enqueue(new Freq(key, map.get(key)));
            }
        }

        LinkedList<Integer> res = new LinkedList<>();
        while(!pq.isEmpty())
            res.add(pq.dequeue().e);
        return res;
    }

    private static void printList(List<Integer> nums){
        for(Integer num: nums)
            System.out.print(num + " ");
        System.out.println();
    }

    public static void main(String[] args) {

        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;
        printList((new Solution()).topKFrequent(nums, k));
    }
}