国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

數(shù)據(jù)結(jié)構(gòu)與算法——堆的應(yīng)用

zhiwei / 1370人閱讀

摘要:我們可以維護(hù)一個(gè)大小為的小頂堆,然后依次遍歷數(shù)組,如果數(shù)組數(shù)據(jù)比堆頂元素大,則插入到堆中,如果小,則不做處理。我們可以維護(hù)一個(gè)大頂堆,一個(gè)小頂堆,小頂堆中存儲(chǔ)后個(gè)數(shù)據(jù),大頂堆中存儲(chǔ)前面剩余的數(shù)據(jù)。

1.  概述

前面說(shuō)完了堆這種數(shù)據(jù)結(jié)構(gòu),并且講到了它很經(jīng)典的一個(gè)應(yīng)用:堆排序,其實(shí)堆這種數(shù)據(jù)結(jié)構(gòu)還有其他很多的應(yīng)用,今天就一起來(lái)看看,主要有下列內(nèi)容:

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

求 Top K 問(wèn)題

求中位數(shù)

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

優(yōu)先級(jí)隊(duì)列是一種特殊的隊(duì)列,前面學(xué)習(xí)隊(duì)列的時(shí)候,說(shuō)到隊(duì)列滿足 先進(jìn)先出,后進(jìn)后出 的特點(diǎn),優(yōu)先級(jí)隊(duì)列則不是這樣。優(yōu)先級(jí)隊(duì)列中的數(shù)據(jù),出隊(duì)的順序是有優(yōu)先級(jí)的,優(yōu)先級(jí)高的,先出隊(duì)列。

而堆其實(shí)就可以看作是一個(gè)優(yōu)先級(jí)隊(duì)列,因?yàn)槎秧斣乜偸菙?shù)據(jù)中最大或最小的元素,每次出隊(duì)列都可以看作取出堆頂元素。

如果你熟悉 Java 語(yǔ)言,則或多或少聽(tīng)說(shuō)或是使用過(guò) PriorityQueue 這個(gè)容器,在《Java 核心技術(shù)·卷 I》中,說(shuō)到 PriorityQueue 就是優(yōu)先級(jí)隊(duì)列,并且它基于一種很優(yōu)雅的數(shù)據(jù)結(jié)構(gòu)——堆。

接下來(lái)就小試牛刀,舉一個(gè)具體的例子來(lái)看看優(yōu)先級(jí)隊(duì)列的應(yīng)用。例如我們需要合并 10 個(gè)有序的小文件,小文件中存儲(chǔ)的是有序的字符串?dāng)?shù)據(jù)。借助優(yōu)先級(jí)隊(duì)列,我們可以很高效的解決這個(gè)問(wèn)題。

我們從每個(gè)文件中讀取第一個(gè)字符串存入優(yōu)先級(jí)隊(duì)列中,那么每次出隊(duì)列,都是最小的那個(gè)元素。將出隊(duì)列的數(shù)據(jù)存儲(chǔ)到一個(gè)大文件中,然后繼續(xù)從文件中讀取一個(gè)字符串存入隊(duì)列,然后繼續(xù)出隊(duì)列,一直循環(huán)這個(gè)操作。

當(dāng)然,這主要是針對(duì)數(shù)據(jù)文件較大的情況,如果數(shù)據(jù)不多,那么直接將全部的數(shù)據(jù)存入隊(duì)列,然后依次出隊(duì)列就可以了,具體問(wèn)題具體分析。

3.  Top K 問(wèn)題

這樣的問(wèn)題其實(shí)非常的常見(jiàn)了,在一組數(shù)據(jù)當(dāng)中 ,我們需要求得其前 K 大的數(shù)據(jù)。

這分為了兩種情況,一是針對(duì) 靜態(tài)數(shù)據(jù) ,即數(shù)據(jù)不會(huì)發(fā)生變化。我們可以維護(hù)一個(gè)大小為 K 的小頂堆,然后依次遍歷數(shù)組,如果數(shù)組數(shù)據(jù)比堆頂元素大,則插入到堆中,如果小,則不做處理。遍歷完之后,則堆中存在的數(shù)據(jù)就是 Top K 了。我用代碼模擬了這個(gè)過(guò)程:

public class GetTopK {
    public static void main(String[] args) {
        int[] num = {2, 34, 45, 56, 76, 65, 678, 33, 888, 678, 98, 0, 7};

        //求 Top 3
        Queue queue = new PriorityQueue<>(3);
        queue.add(num[0]);
        queue.add(num[1]);
        queue.add(num[2]);

        for (int i = 3; i < num.length; i++) {
            int small = queue.peek();
            if (num[i] > small){
                queue.poll();
                queue.add(num[i]);
            }
        }
        System.out.println(queue.toString());
    }
}

第二種情況,是動(dòng)態(tài)的數(shù)據(jù)集合,數(shù)據(jù)會(huì)有增加、刪除的情況,如果新增一個(gè)元素,將其和堆頂元素進(jìn)行比較,如果數(shù)據(jù)比堆頂元素大,則插入到堆中,如果小,則不做處理。這樣的話,無(wú)論數(shù)據(jù)怎樣變化,我們都能夠隨時(shí)拿到 Top K,而不用因?yàn)閿?shù)據(jù)的變化重新組織堆。

4.  求中位數(shù)

顧名思義,中位數(shù)就是一組數(shù)據(jù)中最中間的那個(gè)數(shù)據(jù),只不過(guò)注意,數(shù)據(jù)需要有序排列。針對(duì)一個(gè)大小為 n 的數(shù)據(jù)集,如果 n 為偶數(shù),那么中位數(shù)有兩個(gè),分別是 n/2 和 n/2 + 1 這兩個(gè)數(shù)據(jù),我們可以隨機(jī)取其中一個(gè);如果 n 為奇數(shù),則 n/2 + 1 這個(gè)數(shù)為中位數(shù)。

如果是一個(gè)靜態(tài)的數(shù)據(jù),那么可直接排序然后求中位數(shù),但是如果數(shù)據(jù)有變化,這樣每次排序的成本太高了。所以,可以借助堆來(lái)實(shí)現(xiàn)求中位數(shù)的功能。

我們可以維護(hù)一個(gè)大頂堆,一個(gè)小頂堆,小頂堆中存儲(chǔ)后 n/2 個(gè)數(shù)據(jù),大頂堆中存儲(chǔ)前面剩余的數(shù)據(jù)。如果 n 是偶數(shù),則兩個(gè)堆中存儲(chǔ)的都是相同個(gè)數(shù)的數(shù)據(jù),如果 n 為奇數(shù),則大頂堆中要多一個(gè)數(shù)據(jù)。結(jié)合下圖你就很容易明白了:

如果有數(shù)據(jù)插入的情況,如果數(shù)據(jù)小于等于大頂堆頂元素,則插入到大頂堆中,如果數(shù)據(jù)大于等于小頂堆頂元素,則插入到小頂堆中。只不過(guò)可能會(huì)出現(xiàn)一個(gè)問(wèn)題,就是堆中的數(shù)據(jù)不滿足均分情況,那么我們需要移動(dòng)兩個(gè)堆中的元素,反正需要保證 大頂堆的元素個(gè)數(shù)和小頂堆的元素個(gè)數(shù)要么相等,或者大頂堆中多一個(gè)。

我用代碼簡(jiǎn)單模擬了整個(gè)實(shí)現(xiàn):

    public class GetMiddleNum {
        public static void main(String[] args) {
            //原始數(shù)據(jù)
            Integer[] num = {12, 34, 6, 43, 78, 65, 42, 33, 5, 8};
            //排序后存入ArrayList中
            Arrays.sort(num);
            ArrayList data = new ArrayList<>(Arrays.asList(num));
            //大頂堆
            Queue bigQueue = new PriorityQueue<>((o1, o2) -> {
                if (o1 <= o2) return 1;
                else return -1;
            });
            //小頂堆
            Queue smallQueue = new PriorityQueue<>();
    
            int n = data.size();
            int i;
            if (n % 2 == 0) i = n / 2;
            else i = n / 2 + 1;
    
            //后 n/2 的數(shù)據(jù)存入到小頂堆中
            for (int j = i; j < n; j++) {
                smallQueue.add(data.get(j));
            }
            //前面的數(shù)據(jù)存入到大頂堆中
            for (int j = 0; j < i; j++) {
                bigQueue.add(data.get(j));
            }
    
            //插入數(shù)據(jù),需要做多帶帶的處理
            insert(data, 99, bigQueue, smallQueue);
            insert(data, 3, bigQueue, smallQueue);
            insert(data, 1, bigQueue, smallQueue);
    
            //大頂堆的堆頂元素就是中位數(shù)
            System.out.println("The middle num = " + bigQueue.peek());
        }
    
        private static void insert(List list, int value, Queue bigQueue, Queue smallQueue){
            list.add(value);
            if (value <= bigQueue.peek())
                bigQueue.add(value);
            if (value >= smallQueue.peek())
                smallQueue.add(value);
    
            while (smallQueue.size() > bigQueue.size())
                bigQueue.add(smallQueue.poll());
            while (bigQueue.size() - smallQueue.size() > 1)
                smallQueue.add(bigQueue.poll());
        }
    }

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/74081.html

相關(guān)文章

  • JavaScript數(shù)據(jù)結(jié)構(gòu)算法(十一)二叉堆

    摘要:二叉堆數(shù)據(jù)結(jié)構(gòu)是一種特殊的二叉樹(shù),他能高效快速的找出最大值和最小值,常應(yīng)用于優(yōu)先隊(duì)列和著名的堆排序算法中。 二叉堆數(shù)據(jù)結(jié)構(gòu)是一種特殊的二叉樹(shù),他能高效、快速的找出最大值和最小值,常應(yīng)用于優(yōu)先隊(duì)列和著名的堆排序算法中。 二叉堆 二叉堆有以下兩個(gè)特性: 是一顆完全二叉樹(shù),表示數(shù)的每一層都有左側(cè)和右側(cè)子節(jié)點(diǎn)(除最后一層的葉節(jié)點(diǎn)),并且最后一層的葉節(jié)點(diǎn)盡可能是左側(cè)子節(jié)點(diǎn) 二叉堆不是最小堆就是...

    MartinHan 評(píng)論0 收藏0
  • 數(shù)據(jù)結(jié)構(gòu)算法——堆

    摘要:堆排序的時(shí)間復(fù)雜度非常的穩(wěn)定,是,并且是原地排序算法,具體是怎么實(shí)現(xiàn)的呢我們一般把堆排序分為兩個(gè)步驟建堆和排序。 1. 什么是堆 堆(Heap),其實(shí)是一種特殊的二叉樹(shù),主要滿足了二叉樹(shù)的兩個(gè)條件: 堆是一種完全二叉樹(shù),還記得完全二叉樹(shù)的定義嗎?葉節(jié)點(diǎn)都在最底下兩層,最后一層的節(jié)點(diǎn)都靠左排列,并且除了最后一層,其他層的節(jié)點(diǎn)個(gè)數(shù)都要達(dá)到最大,這種樹(shù)叫做完全二叉樹(shù)。 堆中的每個(gè)節(jié)點(diǎn)的值都...

    hankkin 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<