本發(fā)明的實(shí)施例公開(kāi)一種優(yōu)先級(jí)隊(duì)列設(shè)計(jì)方法及優(yōu)先級(jí)隊(duì)列設(shè)計(jì)裝置。優(yōu)先級(jí)隊(duì)列設(shè)計(jì)方法包括：獲取待置于優(yōu)先級(jí)隊(duì)列中的各元素的優(yōu)先級(jí)級(jí)別序列；以得到的優(yōu)先級(jí)級(jí)別序列構(gòu)建優(yōu)先級(jí)隊(duì)列，優(yōu)先級(jí)級(jí)別序列中的每一級(jí)優(yōu)先級(jí)級(jí)別對(duì)應(yīng)構(gòu)建的所述優(yōu)先級(jí)隊(duì)列中的一列元素；為構(gòu)建的所述優(yōu)先級(jí)隊(duì)列中的列元素設(shè)置相應(yīng)的優(yōu)先級(jí)級(jí)別索引，并使設(shè)置的所述優(yōu)先級(jí)級(jí)別索引映射優(yōu)先級(jí)級(jí)別鏈表；從所述待置于優(yōu)先級(jí)隊(duì)列中的各元素中，選取相同優(yōu)先級(jí)級(jí)別的元素，按照先進(jìn)先出的方式，置于該優(yōu)先級(jí)別對(duì)應(yīng)的優(yōu)先級(jí)級(jí)別鏈表中，以使所述優(yōu)先級(jí)級(jí)別鏈表存儲(chǔ)具有該優(yōu)先級(jí)級(jí)別的所有元素。應(yīng)用本發(fā)明，可以降低基于生成的優(yōu)先級(jí)隊(duì)列進(jìn)行更新的時(shí)間復(fù)雜度。

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算機(jī)應(yīng)用技術(shù)，尤其涉及一種優(yōu)先級(jí)隊(duì)列設(shè)計(jì)方法及優(yōu)先級(jí)隊(duì)列設(shè)計(jì)裝置。

背景技術(shù)

在計(jì)算機(jī)應(yīng)用領(lǐng)域中，隊(duì)列是一種被經(jīng)常應(yīng)用的支持先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，例如，被廣泛應(yīng)用于數(shù)據(jù)存儲(chǔ)，優(yōu)先級(jí)隊(duì)列是在支持優(yōu)先級(jí)級(jí)別的情況下，保持先進(jìn)先出操作模式的隊(duì)列，即對(duì)于需要處理的元素，按照優(yōu)先級(jí)級(jí)別對(duì)各元素進(jìn)行排序，對(duì)于優(yōu)先級(jí)級(jí)別相同的元素，按照先進(jìn)先出的方式進(jìn)行排序，從而得到優(yōu)先級(jí)隊(duì)列。優(yōu)先級(jí)隊(duì)列一般適用于要求有序的應(yīng)用場(chǎng)景中，實(shí)際應(yīng)用中，在生成優(yōu)先級(jí)隊(duì)列后，由于元素的動(dòng)態(tài)更新，因而，需要在優(yōu)先級(jí)隊(duì)列中不斷執(zhí)行插入元素、刪除元素等優(yōu)先級(jí)隊(duì)列更新處理，為了保證優(yōu)先級(jí)隊(duì)列的有序，在優(yōu)先級(jí)隊(duì)列中插入新元素和刪除隊(duì)頭元素時(shí)，需要結(jié)合待處理元素優(yōu)先級(jí)級(jí)別以及先進(jìn)先出重新調(diào)整優(yōu)先級(jí)隊(duì)列中已有元素的位置。

在對(duì)優(yōu)先級(jí)隊(duì)列進(jìn)行更新的過(guò)程中，由于優(yōu)先級(jí)隊(duì)列中一個(gè)元素的變動(dòng)可能導(dǎo)致需要對(duì)較多的元素進(jìn)行優(yōu)先級(jí)級(jí)別重排序處理，不僅需要消耗較多的計(jì)算資源，也使得基于生成的優(yōu)先級(jí)隊(duì)列進(jìn)行更新所耗費(fèi)的時(shí)間較長(zhǎng)，此外，在對(duì)優(yōu)先級(jí)隊(duì)列整的元素進(jìn)行查詢時(shí)，其查詢時(shí)間也與優(yōu)先級(jí)隊(duì)列的排序策略相關(guān)。因此，如何更有效地生成優(yōu)先級(jí)隊(duì)列，減少查詢以及更新優(yōu)先級(jí)隊(duì)列中元素所需的時(shí)間，花費(fèi)較小的代價(jià)，使得生成的優(yōu)先級(jí)隊(duì)列能快速高效地支持插入元素和刪除元素等更新處理，提升用戶的業(yè)務(wù)體驗(yàn)，是研究?jī)?yōu)先級(jí)隊(duì)列的一個(gè)熱點(diǎn)問(wèn)題。

目前，對(duì)于C++標(biāo)準(zhǔn)模板庫(kù)(STL，Standard Template Library)和Java中的優(yōu)先級(jí)隊(duì)列生成和更新，是基于堆來(lái)實(shí)現(xiàn)的。其中，堆是一種樹形數(shù)據(jù)結(jié)構(gòu)，是優(yōu)先級(jí)隊(duì)列中的一種，每個(gè)結(jié)點(diǎn)都有一個(gè)值，堆的特點(diǎn)是根結(jié)點(diǎn)的值最小(或最大)，且根結(jié)點(diǎn)的兩個(gè)子樹也是一個(gè)堆。由于堆在添加元素與刪除元素時(shí)都會(huì)破壞堆結(jié)構(gòu)，并只允許在優(yōu)先級(jí)隊(duì)列的前端(隊(duì)頭)進(jìn)行刪除操作，而在優(yōu)先級(jí)隊(duì)列的后端(隊(duì)尾)進(jìn)行插入操作。因而，添加元素與刪除元素都需要進(jìn)行堆結(jié)構(gòu)調(diào)整，在堆結(jié)構(gòu)調(diào)整中，需要按照優(yōu)先級(jí)級(jí)別算法以及先進(jìn)先出原則，將添加的元素插入優(yōu)先級(jí)隊(duì)列中該添加元素優(yōu)先級(jí)對(duì)應(yīng)的位置，在刪除元素時(shí)，從第一個(gè)(即最小元素，優(yōu)先級(jí)最高)元素開(kāi)始，即取隊(duì)頭元素執(zhí)行刪除操作。這樣，通過(guò)堆實(shí)現(xiàn)C++STL和Java中的優(yōu)先級(jí)隊(duì)列生成和更新，可以保證優(yōu)先級(jí)隊(duì)列中優(yōu)先級(jí)高的先服務(wù)，而非先入先服務(wù)。但該基于優(yōu)先級(jí)級(jí)別算法以及先進(jìn)先出原則生成的優(yōu)先級(jí)隊(duì)列在進(jìn)行更新時(shí)，插入元素和刪除隊(duì)頭元素的時(shí)間復(fù)雜度都是O(logn)，其中，n為優(yōu)先級(jí)隊(duì)列中元素的個(gè)數(shù)。

為了有效降低生成的優(yōu)先級(jí)隊(duì)列在進(jìn)行更新時(shí)所需的時(shí)間，現(xiàn)有技術(shù)中提出了基于鏈表生成優(yōu)先級(jí)隊(duì)列，將各元素按照優(yōu)先級(jí)級(jí)別遞減順序排列。這樣，可以使得在生成的優(yōu)先級(jí)隊(duì)列中插入元素的時(shí)間復(fù)雜度為O(lgn)，而將刪除元素的時(shí)間復(fù)雜度降低為O(l)。但該方法，優(yōu)先級(jí)隊(duì)列整體更新所需的時(shí)間(時(shí)間復(fù)雜度)還是較長(zhǎng)，降低了基于生成的優(yōu)先級(jí)隊(duì)列進(jìn)行更新時(shí)的效率，不能滿足用戶即時(shí)、快速的業(yè)務(wù)處理需求。

發(fā)明內(nèi)容

有鑒于此，本發(fā)明實(shí)施例提供一種優(yōu)先級(jí)隊(duì)列設(shè)計(jì)方法及優(yōu)先級(jí)隊(duì)列設(shè)計(jì)裝置，降低基于生成的優(yōu)先級(jí)隊(duì)列進(jìn)行更新的時(shí)間復(fù)雜度。

為達(dá)到上述目的，本發(fā)明的實(shí)施例采用如下技術(shù)方案：

一方面，本發(fā)明實(shí)施例提供一種優(yōu)先級(jí)隊(duì)列設(shè)計(jì)方法，包括：

獲取待置于優(yōu)先級(jí)隊(duì)列中的各元素的優(yōu)先級(jí)級(jí)別序列；