一 什么是優(yōu)先隊列赊琳？

1?? 優(yōu)先隊列其實就是隊列的一種街夭，不過優(yōu)先隊列是區(qū)別于普通隊列的；普通隊列是一種先進先出躏筏，后進后出的數(shù)據(jù)結(jié)構(gòu)板丽，優(yōu)先隊列和普通隊列的區(qū)別就在于，出隊的順序和入隊的順序無關(guān)趁尼，是和優(yōu)先級息息相關(guān)的埃碱；

優(yōu)先隊列的使用場景1

在這個場景中，由于現(xiàn)在計算機都是多任務(wù)執(zhí)行的酥泞，我們的操作系統(tǒng)會動態(tài)的選擇優(yōu)先級最高的任務(wù)執(zhí)行砚殿；因為我們無法準(zhǔn)確預(yù)估有多少的任務(wù)需要處理，所以我們我們的操作系統(tǒng)只能根據(jù)優(yōu)先級來進行資源的分配芝囤；

2?? 優(yōu)先隊列的底層實現(xiàn)方式：

優(yōu)先隊列的實現(xiàn)方式

普通線性結(jié)構(gòu)(數(shù)組 鏈表)：入隊其實就是一個添加的操作似炎，所以時間復(fù)雜度為O(1);但是出隊的操作由于需要執(zhí)行查詢的操作所以時間復(fù)雜度是O(n)的辛萍；
順序線性結(jié)構(gòu)：與普通線性結(jié)構(gòu)相比，不對的操作是O(1)的羡藐，但是入隊是O(n)的贩毕，因為在入隊的時候我們需要對新插入的元素進行比較以便于確定新插入元素的位置；
堆：堆是一種高效的數(shù)據(jù)結(jié)構(gòu)传睹，用堆來實現(xiàn)優(yōu)先隊列的話它的入隊和出隊時間復(fù)雜度都是O(logn)的級別耳幢，這里說的O(logn)是指在最壞的情況下都是這個級別的。

二 堆的基本表示

二叉堆圖示

說白了，二叉堆就是滿足一些特殊性質(zhì)的二叉樹邢隧；

1?? 二叉堆的特殊性質(zhì)

1. 首先二叉堆是一顆完全二叉樹店印；
   二叉堆特性1
   上圖是一個滿二叉樹，在介紹二分搜索樹的筆記里有關(guān)于滿二叉樹的介紹：滿二叉樹表示出了葉子節(jié)點倒慧，其他的各個節(jié)點都有左右兩個節(jié)點按摘；但是滿二叉樹并不是完全二叉樹
   完全二叉樹圖示
   完全二叉樹：把元素數(shù)據(jù)排列成樹的形狀就是完全二叉樹；所以對于完全二叉樹來說纫谅，樹的右下角可能會有缺失甚至是空的炫贤；

2.在堆中某個節(jié)點的值總是不大于其父節(jié)點的值；

最大堆圖示

注意：從圖中可以看到二叉堆中的某些節(jié)點甚至小于葉子節(jié)點的值付秕，但是這并不影響二叉堆的特性兰珍，在二叉堆中節(jié)點的值和節(jié)點所處的層次之間是沒有關(guān)系的。

只有同時滿足了以上兩個特性才能稱為二叉堆询吴；

2?? 二叉堆的實現(xiàn)方式

1. 我們完全可以使用實現(xiàn)二分搜索樹的方式來實現(xiàn)二叉堆掠河，但是由于二叉堆是通過把元素數(shù)據(jù)按照順序進行排列形成的樹的形狀，所以我們可以使用數(shù)組的方式來實現(xiàn)二叉堆
   二叉堆的實現(xiàn)圖示

   通過這個圖我們可以清楚的看到二叉堆中的各個元素的層級順序是怎樣的猛计，所有我們可以直接使用數(shù)組來實現(xiàn)這樣的一個結(jié)構(gòu)唠摹；

2. 當(dāng)我們使用數(shù)組來實現(xiàn)這樣一個結(jié)構(gòu)的時候我們怎么去表示一個節(jié)點的左右子節(jié)點呢？如果我們使用二分搜索樹那樣的實現(xiàn)方式來實現(xiàn)的話奉瘤，我們可以通過定義節(jié)點的左右子節(jié)點來實現(xiàn)勾拉，但是在數(shù)組中我們顯然不能使用節(jié)點定義這樣的方式；但是通過觀察我們發(fā)現(xiàn)了這樣的一個規(guī)律毛好，就是對于任意個節(jié)點來說望艺，它的左節(jié)點的索引是其父節(jié)點索引的2倍，右節(jié)點是其父節(jié)點索引的2倍+1肌访；
   left child(i) = 2 * I;
   right child(i) = 2 * i + 1;
   使用這樣的方式還有一個好處就是找默，我們可以很容易的通過任意一個節(jié)點找到其父節(jié)點，可以直接使用當(dāng)前節(jié)點除以2就可以找到父節(jié)點吼驶，如果是右節(jié)點的話是需要取整的也就是說需要將小數(shù)部分抹除掉惩激；
   parent(i) = i / 2;
   這就是使用數(shù)組來實現(xiàn)二叉堆的好處店煞，數(shù)組的索引之間是存在這樣的邏輯關(guān)系的；

3. 當(dāng)我們使用數(shù)組來實現(xiàn)這樣的結(jié)構(gòu)時還有一個問題风钻，就是數(shù)組中索引為0的位置該怎么處理顷蟀？之前在實現(xiàn)循環(huán)隊列以及鏈表的時候我們會有意的浪費一個節(jié)點，但是在這里我們不用采用這樣的方式骡技，我們只需要對我們的節(jié)點進行一次偏移的操作就可以了
   parent(i) = (i - 1) / 2;
   left child(i) = 2 * i + 1;
   right child(i) = 2 * i + 2;
   這樣我們就可以直接使用這個索引為0的位置了鸣个；

三 代碼實現(xiàn)最大二叉堆

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<>();
    }

    /**
     * 返回堆中的元素個數(shù)
     * @return
     */
    public int getSize(){
        return data.getSize();
    }

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

    /**
     * 返回完全二叉樹的數(shù)組表示中布朦，一個索引的父節(jié)點索引值
     * @param index
     * @return
     */
    private int parent(int index){
        if (index == 0){
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        }
        return (index - 1) / 2;
    }

    /**
     * 返回完全二叉樹的數(shù)組表示中囤萤，一個父節(jié)點的左節(jié)點的索引值
     * @param index
     * @return
     */
    private int leftChild(int index){
        return index * 2 + 1;
    }

    /**
     * 返回完全二叉樹的數(shù)組表示中，一個父節(jié)點的右節(jié)點的索引值
     * @param index
     * @return
     */
    private int rightChild(int index){
        return index * 2 + 2;
    }
}

四 向堆中添加元素和Sift Up

1?? 添加過程圖示

向堆中添加一個元素1

從樹型結(jié)構(gòu)的角度去看是趴，添加一個元素等于是在樹中增加一個節(jié)點涛舍，但是我們的二叉堆底層是使用數(shù)組實現(xiàn)的，所以向堆中添加元素實際上操作的是數(shù)組

向堆中添加一個元素2

從這張圖片可以看出唆途，添加一個元素就相當(dāng)于在索引為10的位置插入一個元素富雅，但是這樣的操作雖然說滿足了完全二叉樹的結(jié)構(gòu)，但是并沒有滿足某個節(jié)點的值總是不大于其父節(jié)點的值這個特性肛搬，所以我們還需要進行調(diào)整

向堆中添加元素3

調(diào)整也是比較簡單的没佑，因為就算是出現(xiàn)需要調(diào)整的情況也是發(fā)生在新加入的元素與其父節(jié)點以及祖先節(jié)點的這條鏈路上，所以我們只要對這一條鏈路進行調(diào)整即可温赔；

向堆中添加元素4

所以在這里我們將新加入的數(shù)據(jù)以及對應(yīng)的父節(jié)點進行比較图筹，然后進行位置的對調(diào)即可；

向堆中添加元素5

調(diào)整完畢以后我們發(fā)現(xiàn)還是不能完全滿足二叉堆的特性让腹，所以我們繼續(xù)重復(fù)上一步操作進行元素位置的對調(diào)；

向堆中添加元素6

到這里堆中元素的調(diào)整過程就完成了扣溺，

向堆中添加元素7

這個過程就是Sift Up也就是堆中元素的上浮過程骇窍；

2?? 代碼實現(xiàn)

    /**
     * 向堆中添加一個元素
     * @param e
     */
    public void add(E e){
        data.addLast(e);
        // 執(zhí)行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

但是取出的最大值同時也是堆中的根節(jié)點一旦取出就會導(dǎo)致二叉堆結(jié)構(gòu)的不成立，所以我們需要想辦法解決這個問題驱犹，第一種方式是將剩下的兩個堆融合在一起嘲恍，但是這樣做的話會非常麻煩；所以我們采用其他方法來解決這個問題雄驹；

從堆中取出元素3

如圖所示佃牛，我們采用的方式是將最后一個值放到被取出值的位置侍芝；這樣的話我們的二叉堆的根節(jié)點就變成了16镀层，然后我們刪除最后一個節(jié)點

從堆中取出元素4

這樣我們的數(shù)組中就沒有索引為10的元素了脑蠕，從元素個數(shù)的角度看本次操作是成功的薇搁，但是這樣操作以后我們的二叉堆的特性就得不到滿足了，

從堆中取出元素5

這個時候我們就將根節(jié)點與其對應(yīng)的左右子節(jié)點進行對比爷速，如果根節(jié)點小于左右根節(jié)點我們就將根節(jié)點與兩個子節(jié)點中最大的那個進行位置的交換央星；

從堆中取出元素6

在本次示例我們將16與52進行位置上的交換；交換完成以后52這個元素作為根節(jié)點就比它的兩個子節(jié)點都大了惫东；

從堆中取出元素7

由于交換完成以后有可能會出現(xiàn)無法滿足二叉堆特性的情況所以仍要繼續(xù)進行交換莉给；

從堆中取出元素8

交換完成以后的節(jié)點很明顯比其子節(jié)點要大

從堆中取出元素9

然后我們在將16與其子節(jié)點進行對比，由于這一次子節(jié)點只有一個我們只能對比一個廉沮，對比以后發(fā)現(xiàn)子節(jié)點是小于它的父節(jié)點颓遏，同時也是滿足二叉堆的特性的就不進行位置上的交換了；這個過程就叫做Sift Down(數(shù)據(jù)下沉)废封，通過這個操作我們就完成從堆中取出一個數(shù)據(jù)的操作州泊。

2?? 代碼實現(xiàn)

/**
     * 查看堆中的最大元素
     * @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.");
    }

測試結(jié)果

六 Heapify和Replace

1?? Replace

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

2.怎么實現(xiàn)遥皂？
可以先執(zhí)行extractMax操作，在進行一次add操作來實現(xiàn)刽漂，但是這樣的效果不是很好演训，因為這樣的話需要執(zhí)行兩次O(logn)的操作；所以我們使用其他的實現(xiàn)方式：可以將堆頂?shù)脑靥鎿Q以后Sift Down贝咙，這樣的話我們只需要執(zhí)行一次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
將任意數(shù)組整理成堆的形狀庭猩；

2.怎么實現(xiàn)窟她？
遍歷一下數(shù)組，然后將數(shù)組中的元素按照二叉堆的特性進行排序即可蔼水，但是由于這樣做效率會比較低這里并不推薦震糖；

3.更高效的實現(xiàn)。

Heapify圖示1

如圖所示這是一個完全二叉樹趴腋，但是并不滿足二叉堆的特性吊说；

Heapify圖示2

所以我們根據(jù)上圖中的二叉樹找到倒數(shù)第一個非葉子節(jié)點，然后對這個節(jié)點按照倒敘從后往前不斷的進行Sift Down的操作就可以了优炬；但是這里有一個問題就是我們怎么確定倒數(shù)第一個非葉子節(jié)點的索引是多少呢颁井？我們可以從最后一個節(jié)點的位置計算出最后一個非葉子節(jié)點的索引；實現(xiàn)過程請參考圖示：

Heapify圖示3

Heapify圖示4

Heapify圖示5

Heapify圖示6

Heapify圖示7

Heapify圖示8

Heapify圖示9

Heapify圖示10

至此我們的Heapify的操作就完成了雅宾；

4. 代碼實現(xiàn)

/**
     * 構(gòu)造函數(shù)，入?yún)閿?shù)組
     * @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");
    }
}

測試結(jié)果

七 基于堆的優(yōu)先隊列

1?? 實現(xiàn)優(yōu)先隊列接口

package com.mufeng.MaxHeap;

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

    /**
     * 獲取隊列中元素的個數(shù)
     * @return
     */
    int getSize();

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

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

    /**
     * 從隊列中刪除一個元素(出隊)
     * @return
     */
    E dequeues();

    /**
     * 獲取對首的元素
     * @return
     */
    E getFront();
}

2?? 實現(xiàn)優(yōu)先隊列類

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;

    /**
     * 構(gòu)造器
     */
    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();
    }
}

八 練習(xí)

給定一個非空的整數(shù)數(shù)組糊余，返回其中出現(xiàn)頻率前 k 高的元素秀又。
例如单寂，
給定數(shù)組 [1,1,1,2,2,3] , 和 k = 2，返回 [1,2]吐辙。
注意：你可以假設(shè)給定的 k 總是合理的宣决，1 ≤ k ≤ 數(shù)組中不相同的元素的個數(shù)。
你的算法的時間復(fù)雜度必須優(yōu)于 O(n log n) , n 是數(shù)組的大小昏苏。

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;

        // 構(gòu)造函數(shù)尊沸，傳入數(shù)組的容量capacity構(gòu)造Array
        public Array(int capacity){
            data = (E[])new Object[capacity];
            size = 0;
        }

        // 無參數(shù)的構(gòu)造函數(shù)，默認(rèn)數(shù)組的容量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;
        }

        // 獲取數(shù)組的容量
        public int getCapacity(){
            return data.length;
        }

        // 獲取數(shù)組中的元素個數(shù)
        public int getSize(){
            return size;
        }

        // 返回數(shù)組是否為空
        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;
        }

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

        // 查找數(shù)組中元素e所在的索引贤惯，如果不存在元素e洼专，則返回-1
        public int find(E e){
            for(int i = 0 ; i < size ; i ++){
                if(data[i].equals(e))
                    return i;
            }
            return -1;
        }

        // 從數(shù)組中刪除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;
        }

        // 從數(shù)組中刪除第一個元素, 返回刪除的元素
        public E removeFirst(){
            return remove(0);
        }

        // 從數(shù)組中刪除最后一個元素, 返回刪除的元素
        public E removeLast(){
            return remove(size - 1);
        }

        // 從數(shù)組中刪除元素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();
        }

        // 將數(shù)組空間的容量變成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);
        }

        // 返回堆中的元素個數(shù)
        public int size(){
            return data.getSize();
        }

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

        // 返回完全二叉樹的數(shù)組表示中，一個索引所表示的元素的父親節(jié)點的索引
        private int parent(int index){
            if(index == 0)
                throw new IllegalArgumentException("index-0 doesn't have parent.");
            return (index - 1) / 2;
        }

        // 返回完全二叉樹的數(shù)組表示中孵构，一個索引所表示的元素的左孩子節(jié)點的索引
        private int leftChild(int index){
            return index * 2 + 1;
        }

        // 返回完全二叉樹的數(shù)組表示中屁商，一個索引所表示的元素的右孩子節(jié)點的索引
        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); // 在此輪循環(huán)中,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));
    }
}