?博客主頁: 心榮~
?系列專欄:【Java實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)】
?一句短話: 難在堅(jiān)持,貴在堅(jiān)持,成在堅(jiān)持!

一. 堆

1. 堆的概念

如果有一個(gè)關(guān)鍵碼的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉樹的順序存儲(chǔ)方式存儲(chǔ) 在一 個(gè)一維數(shù)組中，并滿足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，則稱為 小堆(或大堆)。將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。

堆的性質(zhì):

• 堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
• 堆總是一棵完全二叉樹。

2. 堆的存儲(chǔ)方式

從堆的概念可知，堆是一棵完全二叉樹，因此可以層序的規(guī)則采用順序的方式來高效存儲(chǔ)，

注意：對(duì)于非完全二叉樹，則不適合使用順序方式進(jìn)行存儲(chǔ)，因?yàn)闉榱四軌蜻€原二叉樹，空間中必須要存儲(chǔ)空節(jié)點(diǎn)，就會(huì)導(dǎo)致空間利用率比較低。

假設(shè)i為節(jié)點(diǎn)在數(shù)組中的下標(biāo)，則有：

• 如果i為0，則i表示的節(jié)點(diǎn)為根節(jié)點(diǎn)，否則i節(jié)點(diǎn)的雙親節(jié)點(diǎn)為 (i - 1)/2
• 如果2 * i + 1 小于節(jié)點(diǎn)個(gè)數(shù)，則節(jié)點(diǎn)i的左孩子下標(biāo)為2 * i + 1，否則沒有左孩子
• 如果2 * i + 2 小于節(jié)點(diǎn)個(gè)數(shù)，則節(jié)點(diǎn)i的右孩子下標(biāo)為2 * i + 2，否則沒有右孩子

3. 堆的創(chuàng)建

【向下調(diào)整】

首先我們需要知道堆的特點(diǎn), 堆的堆頂?shù)脑卮笥?(或小于) 子堆的元素大小，堆的本質(zhì)就是一棵完全二叉樹，堆采用順序存儲(chǔ)的方式來實(shí)現(xiàn), 所以根據(jù)這些特點(diǎn)可以總結(jié)出堆的創(chuàng)建過程。

1. 找到數(shù)組中最后一個(gè)子樹所在位置，注意這里的子樹不包含單獨(dú)的葉子結(jié)點(diǎn)。
2. 對(duì)該子樹進(jìn)行向下調(diào)整，如果要?jiǎng)?chuàng)建的是大根堆，找到該樹兩個(gè)子結(jié)點(diǎn)值較大的結(jié)點(diǎn)與根結(jié)點(diǎn)進(jìn)行比較，如果這個(gè)子結(jié)點(diǎn)比根結(jié)點(diǎn)要大，則交換兩結(jié)點(diǎn)的值，然后再對(duì)被調(diào)整的子結(jié)點(diǎn)作相同的調(diào)整(向下調(diào)整)，直到被調(diào)整的子樹滿足大堆條件或下標(biāo)超出數(shù)組的范圍; 同樣的思路, 如果建立的是小根堆 , 找到該樹兩個(gè)子結(jié)點(diǎn)值較小的結(jié)點(diǎn)與根結(jié)點(diǎn)進(jìn)行比較，如果這個(gè)子結(jié)點(diǎn)比根結(jié)點(diǎn)要小，則交換兩結(jié)點(diǎn)的值 , 然后再對(duì)被調(diào)整的子結(jié)點(diǎn)作相同的調(diào)整(向下調(diào)整)，直到被調(diào)整的子樹滿足大堆條件或下標(biāo)超出數(shù)組的范圍
3. 從最后一棵子樹（該樹不為葉子，最右邊一棵高度為2的子樹）開始調(diào)整，調(diào)整完后再向前找前一棵子樹 , 以此類推, 直至調(diào)整完最后一棵(以堆頂結(jié)點(diǎn)所代表的樹)結(jié)束，按此順序?qū)λ袠溥M(jìn)行向下調(diào)整，此時(shí)(大/小)堆就創(chuàng)建好了。

設(shè)最后一棵子樹根結(jié)點(diǎn)所對(duì)應(yīng)數(shù)組下標(biāo)為parent，其左子樹根結(jié)點(diǎn)為child，堆大小為len，根據(jù)二叉樹的性質(zhì)，下標(biāo)會(huì)滿足child = 2 ? parent + 1 ； parent = (child ? 1 ) / 2 ;

最后一個(gè)結(jié)點(diǎn)下標(biāo)為len?1，其父結(jié)點(diǎn)下標(biāo)為(len?2) / 2 ; 也就是說 , 最后一棵子樹根結(jié)點(diǎn)的下標(biāo)為(len?2) / 2

對(duì)于向下調(diào)整中，以創(chuàng)建大根堆為例，如果一棵子樹右結(jié)點(diǎn)存在且大于左結(jié)點(diǎn)的值，則child++保證child指向的是左右結(jié)點(diǎn)中較大的那一個(gè)

下面給出的是堆的基本成員屬性,

public class MyHeap {
    public int[] elem;
    public int usedSize;//記錄有效元素個(gè)數(shù)
    public static final int DEFAULT_SIZE = 10;//默認(rèn)容量

    public MyHeap() {
        elem = new int[DEFAULT_SIZE];
    }

    //初始化數(shù)組
    public void initElem(int[] array) {
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            usedSize++;
        }
    }
}

代碼實(shí)現(xiàn)創(chuàng)建大根堆,

//調(diào)整數(shù)組元素,創(chuàng)建大根堆
    public void createHeap() {
        //從最后一個(gè)雙親節(jié)點(diǎn)開始向下調(diào)整
        for (int parent = (this.usedSize-1-1)/2; parent >= 0; parent--) {
            //向下調(diào)整
            shiftDown(parent, this.usedSize);
        }
    }

    /**
     * 向下調(diào)整
     * @param parent 每棵樹的根節(jié)點(diǎn)位置
     * @param len 用來判斷每棵子樹調(diào)整的結(jié)束時(shí)機(jī), 位置不能大于len
     */
    public void shiftDown(int parent, int len) {
        //計(jì)算左孩子位置
        int child = parent*2+1;
        //要判斷左孩子是否存在
        while(child < len) {
            //確定右孩子是否存在,確定最大值
            if (child + 1 < len && elem[child] < elem[child+1]) {
                child++;
            }
            //走到這里child指向的一定是左右孩子中較大的
            if(elem[parent] < elem[child]) {
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

【建堆的時(shí)間復(fù)雜度】

建堆的過程是自下而上的，堆的本質(zhì)就是一棵完全二叉樹，不妨設(shè)該二叉樹的高度為h，堆元素個(gè)數(shù)為n，建堆時(shí)需要對(duì)所有高度大于1的子樹進(jìn)行調(diào)整，最壞情況下該堆是一個(gè)滿堆，設(shè)該堆所處層次為x（從1開始），則第x層次的子樹需要調(diào)整h-x次，有2 ^ (h-1)個(gè)結(jié)點(diǎn)，由于只調(diào)整高度大于1的子樹，因此x的范圍為[1,h?1]

調(diào)整的次數(shù)為T(n):

我們發(fā)現(xiàn)T(n)為等比數(shù)列和減去h再加上1，等比數(shù)列求和公式為Sn=a1(1?qn)/(1?q)

? T(n)=2?(1?2h?1)/(?1)?h+1

? T(n)=2 ^ h?h?1

所以，建堆的時(shí)間復(fù)雜度為O(N)。

4. 元素入堆

按照如下步驟完成元素入堆:

1. 先將元素放入到放入堆尾(注意：空間不夠時(shí)需要擴(kuò)容)
2. 將最后新插入的節(jié)點(diǎn)向上調(diào)整，直到滿足堆的性質(zhì)

下面是對(duì)向上調(diào)整的說明:

在數(shù)組最后一個(gè)位置放入一個(gè)元素后，以大根堆為例, 這個(gè)元素所在的子樹就可能不滿足大根堆的條件了, 所以需要對(duì)該結(jié)點(diǎn)進(jìn)行向上調(diào)整，讓這棵子樹再次滿足大根堆, 如果做出了調(diào)整, 就需要一直先向上調(diào)整, 直至滿足條件 ; 所謂向上調(diào)整就是比較 調(diào)整結(jié)點(diǎn)與父親結(jié)點(diǎn) 值的大小，如果該結(jié)點(diǎn)值比較大，則與父親結(jié)點(diǎn)交換值，否則不需調(diào)整，該堆已經(jīng)滿足大根堆條件，因?yàn)榻粨Q后不知道上面的子樹是否為大根堆，所以需要對(duì)交換路徑上所有的結(jié)點(diǎn)進(jìn)行相同的向上調(diào)整，直到調(diào)整完堆頂，過程中出現(xiàn)父親結(jié)點(diǎn)比較大則結(jié)束調(diào)整; 同樣的如果是小根堆，思路是一樣的, 只需要把把 調(diào)整結(jié)點(diǎn)與父親結(jié)點(diǎn) 的比較方式改變一下即可.

下面的實(shí)現(xiàn)代碼以大根堆為例:

public void offer(int val) {
        //判斷空間是不是滿了
        if(isFull()) {
            elem = Arrays.copyOf(elem, 2*elem.length);
        }
        elem[usedSize] = val;
        usedSize++;
        //向上調(diào)整
        shiftUp(usedSize-1);
    }
    public boolean isFull() {
        return usedSize == elem.length;
    }
    public void shiftUp(int child) {
        int parent = (child-1)/2;
        while(child > 0) {
            if (elem[parent] < elem[child]) {
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;
                child = parent;
                parent = (child-1)/2;
            }else{
                break;
            }
        }
    }

5. 元素出堆

注意：出堆的元素一定是堆頂元素

按照如下步驟完成元素出堆:

1. 將堆頂元素與堆尾元素交換，保存并刪除堆尾元素。
2. 將堆中有效數(shù)據(jù)個(gè)數(shù)減少一個(gè)
3. 對(duì)堆頂元素向下調(diào)整，因?yàn)槎秧斀粨Q元素的路徑可能會(huì)破壞大根堆（或小根堆）結(jié)構(gòu)。
4. 返回之前保存的堆尾元素，返回的是刪除元素的值。

下面的實(shí)現(xiàn)代碼以大根堆為例:

//堆的刪除
    public int pop() {
        if(isEmpty()) {
            throw new EmptyHeapException("當(dāng)前堆為空");
        }
        int tmp = elem[0];
        elem[0] = elem[usedSize-1];
        elem[usedSize-1] = tmp;
        usedSize--;

        shiftDown(0, usedSize);
        return tmp;
    }

6. 獲取堆中元素

    //判斷堆是否為空
    public boolean isEmpty() {
        return usedSize == 0;
    }

    //獲取堆中元素
    public int peek() {
        if(isEmpty()) {
            throw new EmptyHeapException();
        }
        return elem[0];
    }

    //清空
    public void clear() {
        usedSize = 0;
    }

    public int size() {
        return usedSize;
    }

二. 優(yōu)先級(jí)堆列(PriorityQueue)

1. 優(yōu)先級(jí)隊(duì)列

在優(yōu)先級(jí)隊(duì)列中，元素被賦予優(yōu)先級(jí)。當(dāng)訪問元素時(shí)，具有最高優(yōu)先級(jí)的元素最先刪除。優(yōu)先隊(duì)列具有最高級(jí)先出 (first in, largest out)的行為特征，通常采用堆數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn); 比如說一個(gè)優(yōu)先隊(duì)列是由小根堆實(shí)現(xiàn)的，則該隊(duì)列優(yōu)先最小的元素出隊(duì)，反之，優(yōu)先隊(duì)列由大根堆實(shí)現(xiàn)，則該隊(duì)列優(yōu)先最大的元素出隊(duì)。

2. PriorityQueue的特性

關(guān)于PriorityQueue的使用要注意：

1. 使用時(shí)必須導(dǎo)入PriorityQueue所在的包，即： import java.util.PriorityQueue;
2. PriorityQueue中放置的元素必須要能夠比較大小，不能插入無法比較大小的對(duì)象，否則會(huì)拋出ClassCastException異常
3. 不能插入null對(duì)象，否則會(huì)拋出NullPointerException
4. 沒有容量限制，可以插入任意多個(gè)元素，其內(nèi)部可以自動(dòng)擴(kuò)容
5. 插入和刪除元素的時(shí)間復(fù)雜度為O(logN)
6. PriorityQueue底層使用了堆數(shù)據(jù)結(jié)構(gòu)
7. PriorityQueue默認(rèn)情況下是小堆 , 如果想要改變使用大根堆實(shí)現(xiàn)，則需要傳入對(duì)象的比較器，或比較器內(nèi)部類或lambda表達(dá)式所實(shí)現(xiàn)的比較器。

3. 集合框架中PriorityQueue的比較方式

集合框架中的PriorityQueue底層使用堆結(jié)構(gòu)，因此其內(nèi)部的元素必須要能夠比較大小，PriorityQueue采用了：
Comparble和Comparator兩種方式。

1. Comparble是默認(rèn)的內(nèi)部比較方式，如果用戶插入自定義類型對(duì)象時(shí)，該類對(duì)象必須要實(shí)現(xiàn)Comparble接口，并覆寫compareTo方法
2. 用戶也可以選擇使用比較器對(duì)象，如果用戶插入自定義類型對(duì)象時(shí)，必須要提供一個(gè)比較器類，讓該類實(shí)現(xiàn)Comparator接口并覆寫compare方法。

    // JDK中PriorityQueue的實(shí)現(xiàn)：
    public class PriorityQueue<E> extends AbstractQueue<E>
            implements java.io.Serializable {
        // ...
        // 默認(rèn)容量
        private static final int DEFAULT_INITIAL_CAPACITY = 11;
        // 內(nèi)部定義的比較器對(duì)象，用來接收用戶實(shí)例化PriorityQueue對(duì)象時(shí)提供的比較器對(duì)象
        private final Comparator<? super E> comparator;
        // 用戶如果沒有提供比較器對(duì)象，使用默認(rèn)的內(nèi)部比較，將comparator置為null
        public PriorityQueue() {
            this(DEFAULT_INITIAL_CAPACITY, null);
        }
        // 如果用戶提供了比較器，采用用戶提供的比較器進(jìn)行比較
        public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
        // Note: This restriction of at least one is not actually needed,
        // but continues for 1.5 compatibility
            if (initialCapacity < 1)
                throw new IllegalArgumentException();
            this.queue = new Object[initialCapacity];
            this.comparator = comparator;
        }
        // ...
        // 向上調(diào)整：
        // 如果用戶沒有提供比較器對(duì)象，采用Comparable進(jìn)行比較
        // 否則使用用戶提供的比較器對(duì)象進(jìn)行比較
        private void siftUp(int k, E x) {
            if (comparator != null)
                siftUpUsingComparator(k, x);
            else
                siftUpComparable(k, x);
        }
        // 使用Comparable
        @SuppressWarnings("unchecked")
        private void siftUpComparable(int k, E x) {
            Comparable<? super E> key = (Comparable<? super E>) x;
            while (k > 0) {
                int parent = (k - 1) >>> 1;
                Object e = queue[parent];
                if (key.compareTo((E) e) >= 0)
                    break;
                queue[k] = e;
                k = parent;
            }
            queue[k] = key;
        }
        // 使用用戶提供的比較器對(duì)象進(jìn)行比較
        @SuppressWarnings("unchecked")
        private void siftUpUsingComparator(int k, E x) {
            
            while (k > 0) {
                int parent = (k - 1) >>> 1;
                Object e = queue[parent];
                if (comparator.compare(x, (E) e) >= 0)
                    break;
                queue[k] = e;
                k = parent;
            }
            queue[k] = x;
        }
    }

下面的代碼是定義一個(gè)的自定義類型, 要將自定義類型入堆, 自定義類型必須實(shí)現(xiàn)Comparble接口; 將第一個(gè)元素入堆時(shí)不涉及比較, 當(dāng)?shù)诙€(gè)元素入堆就會(huì)涉及比較了;

class Person implements Comparable<Person>{
    int age;
    String name;

    public Person(int age, String name) {
        this.age = age;
        this.name = name;
    }

    @Override
    public int compareTo(Person o) {
        return this.age - o.age;
    }

    @Override
    public String toString() {
        return "Person{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }
}
public class Test {
    public static void main(String[] args) {
        PriorityQueue<Person> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(new Person(18,"張三"));
        priorityQueue.offer(new Person(20,"李四"));
    }
}

4. PriorityQueue常用構(gòu)造方法

觀察這三個(gè)構(gòu)造方法的源碼, 其實(shí)在底層是又調(diào)用了含有兩個(gè)參數(shù)的構(gòu)造方法public PriorityQueue(int initialCapacity**,** Comparator<? super E> comparator), 除了設(shè)置容量的參數(shù)外, 另一個(gè)參數(shù)是一個(gè)比較器, 在調(diào)用時(shí)設(shè)置為了null;

構(gòu)造示例:

static void TestPriorityQueue(){
       // 創(chuàng)建一個(gè)空的優(yōu)先級(jí)隊(duì)列，底層默認(rèn)容量是11
        PriorityQueue<Integer> q1 = new PriorityQueue<>();
       // 創(chuàng)建一個(gè)空的優(yōu)先級(jí)隊(duì)列，底層的容量為initialCapacity
        PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
        ArrayList<Integer> list = new ArrayList<>();
        list.add(4);
        list.add(3);
        list.add(2);
        list.add(1);
        // 用ArrayList對(duì)象來構(gòu)造一個(gè)優(yōu)先級(jí)隊(duì)列的對(duì)象
        // q3中已經(jīng)包含了三個(gè)元素
        PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
        System.out.println(q3.size());
        System.out.println(q3.peek());
    }

注意：默認(rèn)情況下，PriorityQueue隊(duì)列是小堆，如果需要大堆需要用戶提供比較器

public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>(new IntCmp());
        priorityQueue1.offer(1);
        priorityQueue1.offer(2);
        priorityQueue1.offer(3);
        System.out.println(priorityQueue1);

        //使用隱藏內(nèi)部類創(chuàng)建基于大根堆的優(yōu)先隊(duì)列
        PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        priorityQueue2.offer(1);
        priorityQueue2.offer(2);
        priorityQueue2.offer(3);
        System.out.println(priorityQueue1);

        //使用lambda表達(dá)式創(chuàng)建基于大根堆的優(yōu)先隊(duì)列
        PriorityQueue<Integer> priorityQueue3 = new PriorityQueue<>((x, y) -> y-x);
        priorityQueue3.offer(1);
        priorityQueue3.offer(2);
        priorityQueue3.offer(3);
        System.out.println(priorityQueue1);
    }

5. PriorityQueue常用操作方法

static void TestPriorityQueue2(){
        int[] arr = {4,1,9,2,8,0,7,3,6,5};
        // 一般在創(chuàng)建優(yōu)先級(jí)隊(duì)列對(duì)象時(shí)，如果知道元素個(gè)數(shù)，建議就直接將底層容量給好
        // 否則在插入時(shí)需要不夠時(shí)要去擴(kuò)容
        // 擴(kuò)容機(jī)制：開辟更大的空間，拷貝元素，這樣效率會(huì)比較低
        PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
        for (int e: arr) {
            q.offer(e);
        }
        System.out.println(q.size()); // 打印優(yōu)先級(jí)隊(duì)列中有效元素個(gè)數(shù)
        System.out.println(q.peek()); // 獲取優(yōu)先級(jí)最高的元素
        // 從優(yōu)先級(jí)隊(duì)列中刪除兩個(gè)元素之和，再次獲取優(yōu)先級(jí)最高的元素
        q.poll();
        q.poll();
        System.out.println(q.size()); // 打印優(yōu)先級(jí)隊(duì)列中有效元素個(gè)數(shù)
        System.out.println(q.peek()); // 獲取優(yōu)先級(jí)最高的元素
        q.offer(0);
        System.out.println(q.peek()); // 獲取優(yōu)先級(jí)最高的元素
        // 將優(yōu)先級(jí)隊(duì)列中的有效元素刪除掉，檢測其是否為空
        q.clear();
        if(q.isEmpty()){
            System.out.println("優(yōu)先級(jí)隊(duì)列已經(jīng)為空!!!");
        }
        else{
            System.out.println("優(yōu)先級(jí)隊(duì)列不為空");
        }
    }

6. PriorityQueue的擴(kuò)容方式

• 如果容量小于64時(shí)，是按照oldCapacity的2倍方式擴(kuò)容的
• 如果容量大于等于64，是按照oldCapacity的1.5倍方式擴(kuò)容的
• 如果容量超過MAX_ARRAY_SIZE，按照Integer.MAX_VALUE大小來進(jìn)行擴(kuò)容

以下是JDK 1.8中，PriorityQueue的擴(kuò)容方式：

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    private void grow(int minCapacity) {
        int oldCapacity = queue.length;
        // Double size if small; else grow by 50%
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                (oldCapacity + 2) :
                (oldCapacity >> 1));
        // overflow-conscious code
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        queue = Arrays.copyOf(queue, newCapacity);
    }
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }

三. Top-k問題

TOP-K問題：即求數(shù)據(jù)集合中前K個(gè)最大的元素或者最小的元素，一般情況下數(shù)據(jù)量都比較大。
比如：專業(yè)前10名、世界500強(qiáng)、富豪榜、游戲中前100的活躍玩家等。

• 思路1:

要處理這個(gè)問題, 我們能想到的最簡單的方式就是排序, 但是如果數(shù)據(jù)量非常大的話, 就不推薦使用排序了, 因?yàn)槲覀冎灰玫綆讉€(gè)元素, 數(shù)據(jù)量很大時(shí)使用排序效率就比較低了;

• 思路2:

使用堆，如求的是前k個(gè)最大的元素，可以創(chuàng)建一個(gè)基于大根堆的優(yōu)先級(jí)隊(duì)列，把所有數(shù)據(jù)入堆，所有元素都入堆之后再出堆k個(gè)元素，這k個(gè)元素就是前k個(gè)最大的元素。

• 思路3:

上面的兩種思路有一個(gè)缺陷就是, 如果數(shù)據(jù)量非常大的話, 效率就會(huì)很低下; Top-k問題標(biāo)準(zhǔn)解決思路如下:

1. 用數(shù)據(jù)集合中前K個(gè)元素來建堆

• 如果找的是前k個(gè)最大的元素，去建小堆
  如果找的是前k個(gè)最小的元素，去建大堆

2. 用剩余的N-K個(gè)元素依次與堆頂元素來比較，

• 求的是前k個(gè)最大元素, 如果比所建小根堆的堆頂元素大, 則替換堆頂元素
  求的是前k個(gè)最小元素, 如果比所建大根堆的堆頂元素大, 則替換堆頂元素

• 將剩余N-K個(gè)元素依次與堆頂元素比完之后，堆中剩余的K個(gè)元素就是所求的前K個(gè)最小或者最大的元素。

時(shí)間復(fù)雜度分析

向上調(diào)整建堆的時(shí)間復(fù)雜度:

[思路2時(shí)間復(fù)雜度分析]:

要將N個(gè)元素都放入到堆中, 每次入堆都需要向上調(diào)整(N*logN);

堆建好后, 將k個(gè)元素出堆, 每次出堆都需要向下調(diào)整(K*logN)

所以時(shí)間復(fù)雜度為O(NlogN+KlogN)

[思路3時(shí)間復(fù)雜度分析]:

建立大小為k的大/小根堆(K*logK)

遍歷剩下的N-K個(gè)元素每個(gè)都和堆頂比較, 最壞的情況下, 每次都需要去調(diào)整((N-K)*logK)

所以時(shí)間復(fù)雜度為O( K*logK+(N-K)logK ) = O(NlogK)

• 通過下面的OJ去理解Top-k問題

在線OJ：面試題 17.14. 最小K個(gè)數(shù)

設(shè)計(jì)一個(gè)算法，找出數(shù)組中最小的k個(gè)數(shù)。以任意順序返回這k個(gè)數(shù)均可。

示例：

輸入： arr = [1,3,5,7,2,4,6,8], k = 4
輸出： [1,2,3,4]

提示：文章來源地址http://www.zghlxwxcb.cn/news/detail-789448.html

• 0 <= len(arr) <= 100000
• 0 <= k <= min(100000, len(arr))

class Solution {
    //方法三: 建立一個(gè)大小為k的大根堆
    public int[] smallestK(int[] arr, int k) {
        if(arr == null || k <= 0) {
            return new int[0];
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });

        for (int i = 0; i < k; i++) {
            maxHeap.offer(arr[i]);
        }

        for (int i = k; i < arr.length; i++) {
            if(arr[i] < maxHeap.peek()) {
                maxHeap.poll();
                maxHeap.offer(arr[i]);
            }
        }
        int[] tmp = new int[k];
        for (int i = 0; i < k; i++) {
            tmp[i] = maxHeap.poll();
        }
        return tmp;
    }

    //方法二: 將數(shù)據(jù)全部入堆
    /*public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            heap.offer(arr[i]);
        }

        int[] tmp = new int[k];
        for (int i = 0; i < k; i++) {
            tmp[i] = heap.poll();
        }
        return tmp;
    }*/

    //方法一: 排序
    /*public int[] smallestK(int[] arr, int k) {
        Arrays.sort(arr);
        int[] tmp = new int[k];
        for(int i = 0; i < k; i++) {
            tmp[i] = arr[i];
        }
        return tmp;
    }*/
}

到了這里，關(guān)于【JavaDS】優(yōu)先級(jí)隊(duì)列(PriorityQueue),堆,Top-k問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！