C#實(shí)現(xiàn)優(yōu)先隊(duì)列和堆排序
優(yōu)先隊(duì)列
許多應(yīng)用程序都需要處理有序的元素,但不一定要求它們?nèi)坑行?,或是不一定要一次就將它們排序。很多情況下是收集一些元素,處理當(dāng)前鍵值最大的元素,然后再收集更多的元素,再處理當(dāng)前鍵值最大的元素。這種情況下,需要的數(shù)據(jù)結(jié)構(gòu)支持兩種操作:刪除最大的元素和插入元素。這種數(shù)據(jù)結(jié)構(gòu)類(lèi)型叫優(yōu)先隊(duì)列。
這里,優(yōu)先隊(duì)列基于二叉堆數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn),用數(shù)組保存元素并按照一定條件排序,以實(shí)現(xiàn)對(duì)數(shù)級(jí)別的刪除和插入操作。
1.API
優(yōu)先隊(duì)列是一種抽象數(shù)據(jù)類(lèi)型,它表示了一組值和對(duì)這些值的操作,抽象層使應(yīng)用和實(shí)現(xiàn)隔離開(kāi)來(lái)。
2.初級(jí)實(shí)現(xiàn)
- 1.無(wú)序數(shù)組實(shí)現(xiàn)
優(yōu)先隊(duì)列的 insert 方法和下壓棧的 push 方法一樣。刪除最大元素時(shí),遍歷數(shù)組找出最大元素,和邊界元素交換。 - 2.有序數(shù)組實(shí)現(xiàn)
插入元素時(shí),將較大的元素向右移一格(和插入排序一樣)。這樣刪除時(shí),就可以直接 pop。
使用鏈接也是一樣的邏輯。
這些實(shí)現(xiàn)總有一種操作需要線性級(jí)別的時(shí)間復(fù)雜度。使用二叉堆可以保證操作在對(duì)數(shù)級(jí)別的時(shí)間完成。
3.堆的定義
數(shù)據(jù)結(jié)構(gòu)二叉堆可以很好地實(shí)現(xiàn)優(yōu)先隊(duì)列地基本操作。在二叉堆數(shù)組中,每個(gè)元素都要保證大于等于另兩個(gè)特定位置地元素。同樣,這兩個(gè)位置地元素又至少要大于等于數(shù)組中另外兩個(gè)元素,以此類(lèi)推。用二叉樹(shù)表示:
當(dāng)一棵二叉樹(shù)的每個(gè)結(jié)點(diǎn)都大于等于它的兩個(gè)子節(jié)點(diǎn)時(shí),它被成為堆有序。從任意結(jié)點(diǎn)向上,都能得到一列非遞減的元素;從任意結(jié)點(diǎn)向下,都能得到一列非遞增的元素。根結(jié)點(diǎn)是堆有序的二叉樹(shù)中最大的結(jié)點(diǎn)。
二叉堆表示法
這里使用完全二叉樹(shù)表示:將二叉樹(shù)的結(jié)點(diǎn)按照層級(jí)順序(從上到下,從左往右)放入數(shù)組中,不使用數(shù)組的第一個(gè)位置(為了方便計(jì)算),根結(jié)點(diǎn)在位置 1 ,它的子結(jié)點(diǎn)在位置 2 和 3,子結(jié)點(diǎn)的子結(jié)點(diǎn)分別在位置 4,5,6,7,一次類(lèi)推。
在一個(gè)二叉堆中,位置 k 的結(jié)點(diǎn)的父節(jié)點(diǎn)位置在 k/2,而它的兩個(gè)子結(jié)點(diǎn)在 2k 和 2k + 1??梢酝ㄟ^(guò)計(jì)算數(shù)組的索引而不是指針就可以在樹(shù)中上下移動(dòng)。
一棵大小為 N 的完全二叉樹(shù)的高度為 lgN。
4.堆的算法
用長(zhǎng)度為 N+1 的私有數(shù)組 pq[ ] 表示一個(gè)大小為 N 的堆。
堆在進(jìn)行插入或刪除操作時(shí),會(huì)打破堆的狀態(tài),需要遍歷堆并按照要求將堆的狀態(tài)恢復(fù)。這個(gè)過(guò)程稱(chēng)為 堆的有序化。
堆的有序化分為兩種情況:當(dāng)某個(gè)結(jié)點(diǎn)的優(yōu)先級(jí)上升(或在堆底加入一個(gè)新的元素)時(shí),需要由下至上恢復(fù)堆的順序;當(dāng)某個(gè)結(jié)點(diǎn)的優(yōu)先級(jí)下降(例如將根節(jié)點(diǎn)替換為一個(gè)較小的元素),需要由上至下恢復(fù)堆的順序。
上?。ㄓ上轮辽系亩训挠行蚧?/h4>
當(dāng)某個(gè)結(jié)點(diǎn)比它的父結(jié)點(diǎn)更大時(shí),交換它和它的父節(jié)點(diǎn),這個(gè)結(jié)點(diǎn)交換到它父節(jié)點(diǎn)的位置。但有可能比它現(xiàn)在的父節(jié)點(diǎn)大,需要繼續(xù)上浮,直到遇到比它大的父節(jié)點(diǎn)。(這里不需要比較這個(gè)子結(jié)點(diǎn)和同級(jí)的另一個(gè)子結(jié)點(diǎn),因?yàn)榱硪粋€(gè)子結(jié)點(diǎn)比它們的父結(jié)點(diǎn)小)
//上浮 private void Swim(int n) { while (n > 1 && Less(n / 2, n)) { Exch(n/2,n); n = n / 2; } }
下沉(由上至下的堆的有序化)
當(dāng)某個(gè)結(jié)點(diǎn) k 變得比它的兩個(gè)子結(jié)點(diǎn)(2k 和 2k+1)更小時(shí),可以通過(guò)將它和它的兩個(gè)子結(jié)點(diǎn)較大者交換來(lái)恢復(fù)堆有序。交換后在子結(jié)點(diǎn)處可能繼續(xù)打破堆有序,需要繼續(xù)重復(fù)下沉,直到它的子結(jié)點(diǎn)都比它小或到達(dá)底部。
//下沉 private void Sink(int k) { while (2 * k <= N) { int j = 2 * k; //取最大的子節(jié)點(diǎn) if (j < N && Less(j, j + 1)) j++; //如果父節(jié)點(diǎn)不小子節(jié)點(diǎn),退出循環(huán) if (!Less(k,j)) break; //否則交換,繼續(xù)下沉 Exch(j,k); k = j; } }
知道了上浮和下沉的邏輯,就可以很好理解在二叉堆中插入和刪除元素的邏輯。
插入元素:將新元素加到數(shù)組末尾,增加堆的大小并讓這個(gè)新元素上浮到合適的位置。
刪除最大元素:從數(shù)組頂端(即 pq[1])刪除最大元素,并將數(shù)組最后一個(gè)元素放到頂端,減少數(shù)組大小并讓這個(gè)元素下沉到合適位置。
public class MaxPriorityQueue { private IComparable[] pq; public int N; public MaxPriorityQueue(int maxN) { pq = new IComparable[maxN+1]; } public bool IsEmpty() { return N == 0; } public void Insert(IComparable value) { pq[++N] = value; Swim(N); } public IComparable DeleteMax() { IComparable max = pq[1]; Exch(1,N--); pq[N + 1] = null; Sink(1); return max; } //下沉 private void Sink(int k) { while (2 * k <= N) { int j = 2 * k; //取最大的子節(jié)點(diǎn) if (j < N && Less(j, j + 1)) j++; //如果父節(jié)點(diǎn)不小子節(jié)點(diǎn),退出循環(huán) if (!Less(k,j)) break; //否則交換,繼續(xù)下沉 Exch(j,k); k = j; } } //上浮 private void Swim(int n) { while (n > 1 && Less(n / 2, n)) { Exch(n/2,n); n = n / 2; } } private void Exch(int i, int j) { IComparable temp = pq[i]; pq[i] = pq[j]; pq[j] = temp; } private bool Less(int i, int j) { return pq[i].CompareTo(pq[j]) < 0; } }
上述算法對(duì)優(yōu)先隊(duì)列的實(shí)現(xiàn)能夠保證插入和刪除最大元素這兩個(gè)操作的用時(shí)和隊(duì)列的大小成對(duì)數(shù)關(guān)系。這里省略了動(dòng)態(tài)調(diào)整數(shù)組大小的代碼,可以參考下壓棧。
對(duì)于一個(gè)含有 N 個(gè)元素的基于堆的優(yōu)先隊(duì)列,插入元素操作只需要不超過(guò)(lgN + 1)次比較,因?yàn)?N 可能不是 2 的冪。刪除最大元素的操作需要不超過(guò) 2lgN次比較(兩個(gè)子結(jié)點(diǎn)的比較和父結(jié)點(diǎn)與較大子節(jié)點(diǎn)的比較)。
對(duì)于需要大量混雜插入和刪除最大元素的操作,優(yōu)先隊(duì)列很適合。
改進(jìn)
- 1.多叉堆
基于數(shù)組表示的完全三叉樹(shù):對(duì)于數(shù)組 1 至 N 的 N 個(gè)元素,位置 k 的結(jié)點(diǎn)大于等于位于 3k-1, 3k ,3k +1 的結(jié)點(diǎn),小于等于位于 (k+1)/ 3 的結(jié)點(diǎn)。 - 2.調(diào)整數(shù)組大小
使用動(dòng)態(tài)數(shù)組,可以構(gòu)造一個(gè)無(wú)需關(guān)注隊(duì)列大小的優(yōu)先隊(duì)列。可以參考下壓棧。 - 3.索引優(yōu)先隊(duì)列
在許多應(yīng)用程序中,允許客戶(hù)端引用優(yōu)先級(jí)隊(duì)列中已經(jīng)存在的項(xiàng)目是有意義的。一種簡(jiǎn)單的方法是將唯一的整數(shù)索引與每個(gè)項(xiàng)目相關(guān)聯(lián)。
堆排序
我們可以把任意優(yōu)先隊(duì)列變成一種排序方法:先將所有元素插入一個(gè)查找最小元素的優(yōu)先隊(duì)列,再重復(fù)調(diào)用刪除操作刪除最小元素來(lái)將它們按順序刪除。這種排序成為堆排序。
堆排序的第一步是堆的構(gòu)造,第二步是下沉排序階段。
1.堆的構(gòu)造
簡(jiǎn)單的方法是利用前面優(yōu)先隊(duì)列插入元素的方法,從左到右遍歷數(shù)組調(diào)用Swim 方法(由上算法所需時(shí)間和 N logN 成正比)。一個(gè)更聰明高效的方法是,從右(中間位置)到左調(diào)用Sink 方法,只需遍歷一半數(shù)組,因?yàn)榱硪话胧谴笮?1 的堆。這種方法只需少于 2N 次比較和 少于 N 次交換。(堆的構(gòu)造過(guò)程中處理的堆都比較小。例如,要構(gòu)造一個(gè) 127 個(gè)元素的數(shù)組,需要處理 32 個(gè)大小為 3 的堆, 16 個(gè)大小為 7 的堆,8 個(gè)大小為 15 的堆, 4 個(gè)大小為 31 的堆, 2 個(gè)大小為 63 的堆和 1 個(gè)大小為127的堆,因此在最壞情況下,需要 32*1 + 16*2 + 8*3 + 4*4 + 2*5 + 1*6 = 120 次交換,以及兩倍的比較)。
2.下沉排序
堆排序的主要工作在第二階段。將堆中最大元素和堆底元素交換,并下沉至 N--。相當(dāng)于刪除最大元素并將堆底元素放至堆頂(優(yōu)先隊(duì)列刪除操作),將刪除的最大元素放入空出的數(shù)組位置。
public class MaxPriorityQueueSort { public static void Sort(IComparable[] pq) { int n = pq.Length; for (var k = n / 2; k >= 1; k--) { Sink(pq, k, n); } //上浮需要遍歷全部 //for (var k = n; k >= 1; k--) //{ // Swim(pq, k); //} while (n > 1) { Exch(pq,1,n--); Sink(pq,1,n); } } private static void Swim(IComparable[] pq, int n) { while (n > 1 && Less(pq,n / 2, n)) { Exch(pq,n / 2, n); n = n / 2; } } //下沉 private static void Sink(IComparable[] pq,int k, int N) { while (2 * k <= N) { int j = 2 * k; //取最大的子節(jié)點(diǎn) if (j < N && Less(pq,j, j + 1)) j++; //如果父節(jié)點(diǎn)不小子節(jié)點(diǎn),退出循環(huán) if (!Less(pq, k,j)) break; //否則交換,繼續(xù)下沉 Exch(pq, j,k); k = j; } } private static void Exch(IComparable[] pq, int i, int j) { IComparable temp = pq[i-1]; pq[i - 1] = pq[j - 1]; pq[j - 1] = temp; } private static bool Less(IComparable[] pq, int i, int j) { return pq[i - 1].CompareTo(pq[j - 1]) < 0; } public static void Show(IComparable[] a) { for (var i = 0; i < a.Length; i++) Console.WriteLine(a[i]); } }
堆排序的軌跡
將 N 個(gè)元素排序,堆排序只需少于 (2N lgN + 2N)次比較以及一半次數(shù)的交換。2N 來(lái)自堆的構(gòu)造,2N lgN 是每次下沉操作最多需要 2lgN 次比較。
先下沉后上浮
在排序過(guò)程中,大多數(shù)重新插入堆中的項(xiàng)目都會(huì)一直到達(dá)底部。因此,通過(guò)避免檢查元素是否已到達(dá)其位置,可以簡(jiǎn)單地提升兩個(gè)子結(jié)點(diǎn)中的較大者直到到達(dá)底部,然后上浮到適當(dāng)位置,從而節(jié)省時(shí)間。這個(gè)方法將比較數(shù)減少了2倍,但需要額外的簿空間。只有當(dāng)比較操作代價(jià)較高時(shí)可以使用這種方法。(例如將字符串或其他鍵值較長(zhǎng)類(lèi)型的元素排序)。
堆排序是能夠同時(shí)最優(yōu)利用空間和時(shí)間的方法,在最壞情況下也能保證 ~2N lgN 次比較和恒定的額外空間。當(dāng)空間緊張時(shí),可以使用堆排序。但堆排序無(wú)法利用緩存。因?yàn)樗臄?shù)組元素很少喝相鄰的其他元素比較,因此緩存未命中的次數(shù)要遠(yuǎn)高于大多數(shù)比較都在相鄰元素之間進(jìn)行的算法。
到此這篇關(guān)于C#實(shí)現(xiàn)優(yōu)先隊(duì)列和堆排序的文章就介紹到這了。希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
C#實(shí)現(xiàn)Excel表數(shù)據(jù)導(dǎo)入Sql Server數(shù)據(jù)庫(kù)中的方法
這篇文章主要介紹了C#實(shí)現(xiàn)Excel表數(shù)據(jù)導(dǎo)入Sql Server數(shù)據(jù)庫(kù)中的方法,結(jié)合實(shí)例形式詳細(xì)分析了C#讀取Excel表數(shù)據(jù)及導(dǎo)入Sql Server數(shù)據(jù)庫(kù)的具體操作步驟與相關(guān)操作技巧,需要的朋友可以參考下2017-05-05C#使用LINQ查詢(xún)操作符實(shí)例代碼(二)
這篇文章介紹了C#使用LINQ查詢(xún)操作符的方法,文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-06-06C# 循環(huán)判斷會(huì)進(jìn)來(lái)幾次的實(shí)現(xiàn)代碼
這篇文章主要介紹了C# 循環(huán)判斷會(huì)進(jìn)來(lái)幾次的實(shí)現(xiàn)代碼,代碼中就一個(gè)循環(huán),循環(huán)的判斷是從一個(gè)函數(shù)獲取值,需要的朋友可以參考下2018-06-06