C#實現優(yōu)先隊列和堆排序
優(yōu)先隊列
許多應用程序都需要處理有序的元素，但不一定要求它們全部有序，或是不一定要一次就將它們排序。很多情況下是收集一些元素，處理當前鍵值最大的元素，然后再收集更多的元素，再處理當前鍵值最大的元素。這種情況下，需要的數據結構支持兩種操作：刪除最大的元素和插入元素。這種數據結構類型叫優(yōu)先隊列。
這里，優(yōu)先隊列基于二叉堆數據結構實現，用數組保存元素并按照一定條件排序，以實現對數級別的刪除和插入操作。
1.API
優(yōu)先隊列是一種抽象數據類型，它表示了一組值和對這些值的操作，抽象層使應用和實現隔離開來。
2.初級實現
- 1.無序數組實現
優(yōu)先隊列的 insert 方法和下壓棧的 push 方法一樣。刪除最大元素時，遍歷數組找出最大元素，和邊界元素交換。 - 2.有序數組實現
插入元素時，將較大的元素向右移一格（和插入排序一樣）。這樣刪除時，就可以直接 pop。
使用鏈接也是一樣的邏輯。
這些實現總有一種操作需要線性級別的時間復雜度。使用二叉堆可以保證操作在對數級別的時間完成。
3.堆的定義
數據結構二叉堆可以很好地實現優(yōu)先隊列地基本操作。在二叉堆數組中，每個元素都要保證大于等于另兩個特定位置地元素。同樣，這兩個位置地元素又至少要大于等于數組中另外兩個元素，以此類推。用二叉樹表示：
當一棵二叉樹的每個結點都大于等于它的兩個子節(jié)點時，它被成為堆有序。從任意結點向上，都能得到一列非遞減的元素；從任意結點向下，都能得到一列非遞增的元素。根結點是堆有序的二叉樹中最大的結點。
二叉堆表示法
這里使用完全二叉樹表示：將二叉樹的結點按照層級順序（從上到下，從左往右）放入數組中，不使用數組的第一個位置（為了方便計算），根結點在位置 1 ，它的子結點在位置 2 和 3，子結點的子結點分別在位置 4，5，6，7，一次類推。
在一個二叉堆中，位置 k 的結點的父節(jié)點位置在 k/2，而它的兩個子結點在 2k 和 2k + 1?？梢酝ㄟ^計算數組的索引而不是指針就可以在樹中上下移動。
一棵大小為 N 的完全二叉樹的高度為 lgN。
4.堆的算法
用長度為 N+1 的私有數組 pq[ ] 表示一個大小為 N 的堆。
堆在進行插入或刪除操作時，會打破堆的狀態(tài)，需要遍歷堆并按照要求將堆的狀態(tài)恢復。這個過程稱為 堆的有序化。
堆的有序化分為兩種情況：當某個結點的優(yōu)先級上升（或在堆底加入一個新的元素）時，需要由下至上恢復堆的順序；當某個結點的優(yōu)先級下降（例如將根節(jié)點替換為一個較小的元素），需要由上至下恢復堆的順序。
上?。ㄓ上轮辽系亩训挠行蚧?/h4>
當某個結點比它的父結點更大時，交換它和它的父節(jié)點，這個結點交換到它父節(jié)點的位置。但有可能比它現在的父節(jié)點大，需要繼續(xù)上浮，直到遇到比它大的父節(jié)點。（這里不需要比較這個子結點和同級的另一個子結點，因為另一個子結點比它們的父結點?。?/p>
//上浮
private void Swim(int n)
{
while (n > 1 && Less(n / 2, n))
{
Exch(n/2,n);
n = n / 2;
}
}
下沉（由上至下的堆的有序化）
當某個結點 k 變得比它的兩個子結點（2k 和 2k+1）更小時，可以通過將它和它的兩個子結點較大者交換來恢復堆有序。交換后在子結點處可能繼續(xù)打破堆有序，需要繼續(xù)重復下沉，直到它的子結點都比它小或到達底部。
//下沉
private void Sink(int k)
{
while (2 * k <= N)
{
int j = 2 * k;
//取最大的子節(jié)點
if (j < N && Less(j, j + 1))
j++;
//如果父節(jié)點不小子節(jié)點，退出循環(huán)
if (!Less(k,j))
break;
//否則交換，繼續(xù)下沉
Exch(j,k);
k = j;
}
}
知道了上浮和下沉的邏輯，就可以很好理解在二叉堆中插入和刪除元素的邏輯。
插入元素：將新元素加到數組末尾，增加堆的大小并讓這個新元素上浮到合適的位置。
刪除最大元素：從數組頂端（即 pq[1]）刪除最大元素，并將數組最后一個元素放到頂端，減少數組大小并讓這個元素下沉到合適位置。
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é)點
if (j < N && Less(j, j + 1))
j++;
//如果父節(jié)點不小子節(jié)點，退出循環(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;
}
}
上述算法對優(yōu)先隊列的實現能夠保證插入和刪除最大元素這兩個操作的用時和隊列的大小成對數關系。這里省略了動態(tài)調整數組大小的代碼，可以參考下壓棧。
對于一個含有 N 個元素的基于堆的優(yōu)先隊列，插入元素操作只需要不超過（lgN + 1）次比較，因為 N 可能不是 2 的冪。刪除最大元素的操作需要不超過 2lgN次比較（兩個子結點的比較和父結點與較大子節(jié)點的比較）。
對于需要大量混雜插入和刪除最大元素的操作，優(yōu)先隊列很適合。
改進
- 1.多叉堆
基于數組表示的完全三叉樹：對于數組 1 至 N 的 N 個元素，位置 k 的結點大于等于位于 3k-1, 3k ,3k +1 的結點，小于等于位于 （k+1）/ 3 的結點。 - 2.調整數組大小
使用動態(tài)數組，可以構造一個無需關注隊列大小的優(yōu)先隊列。可以參考下壓棧。 - 3.索引優(yōu)先隊列
在許多應用程序中，允許客戶端引用優(yōu)先級隊列中已經存在的項目是有意義的。一種簡單的方法是將唯一的整數索引與每個項目相關聯(lián)。
堆排序
我們可以把任意優(yōu)先隊列變成一種排序方法：先將所有元素插入一個查找最小元素的優(yōu)先隊列，再重復調用刪除操作刪除最小元素來將它們按順序刪除。這種排序成為堆排序。
堆排序的第一步是堆的構造，第二步是下沉排序階段。
1.堆的構造
簡單的方法是利用前面優(yōu)先隊列插入元素的方法，從左到右遍歷數組調用Swim 方法（由上算法所需時間和 N logN 成正比）。一個更聰明高效的方法是，從右（中間位置）到左調用Sink 方法，只需遍歷一半數組，因為另一半是大小為 1 的堆。這種方法只需少于 2N 次比較和 少于 N 次交換。（堆的構造過程中處理的堆都比較小。例如，要構造一個 127 個元素的數組，需要處理 32 個大小為 3 的堆， 16 個大小為 7 的堆，8 個大小為 15 的堆， 4 個大小為 31 的堆， 2 個大小為 63 的堆和 1 個大小為127的堆，因此在最壞情況下，需要 32*1 + 16*2 + 8*3 + 4*4 + 2*5 + 1*6 = 120 次交換，以及兩倍的比較）。
2.下沉排序
堆排序的主要工作在第二階段。將堆中最大元素和堆底元素交換，并下沉至 N--。相當于刪除最大元素并將堆底元素放至堆頂（優(yōu)先隊列刪除操作），將刪除的最大元素放入空出的數組位置。
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é)點
if (j < N && Less(pq,j, j + 1))
j++;
//如果父節(jié)點不小子節(jié)點，退出循環(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 個元素排序，堆排序只需少于 （2N lgN + 2N）次比較以及一半次數的交換。2N 來自堆的構造，2N lgN 是每次下沉操作最多需要 2lgN 次比較。
先下沉后上浮
在排序過程中，大多數重新插入堆中的項目都會一直到達底部。因此，通過避免檢查元素是否已到達其位置，可以簡單地提升兩個子結點中的較大者直到到達底部，然后上浮到適當位置，從而節(jié)省時間。這個方法將比較數減少了2倍，但需要額外的簿空間。只有當比較操作代價較高時可以使用這種方法。（例如將字符串或其他鍵值較長類型的元素排序）。
堆排序是能夠同時最優(yōu)利用空間和時間的方法，在最壞情況下也能保證 ~2N lgN 次比較和恒定的額外空間。當空間緊張時，可以使用堆排序。但堆排序無法利用緩存。因為它的數組元素很少喝相鄰的其他元素比較，因此緩存未命中的次數要遠高于大多數比較都在相鄰元素之間進行的算法。
到此這篇關于C#實現優(yōu)先隊列和堆排序的文章就介紹到這了。希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
C#實現Excel表數據導入Sql Server數據庫中的方法
這篇文章主要介紹了C#實現Excel表數據導入Sql Server數據庫中的方法,結合實例形式詳細分析了C#讀取Excel表數據及導入Sql Server數據庫的具體操作步驟與相關操作技巧,需要的朋友可以參考下2017-05-05
這篇文章介紹了C#?Razor的語法規(guī)則，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-01-01
這篇文章介紹了C#使用LINQ查詢操作符的方法，文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-06-06
ASP.NET連接數據庫的技術叫ADO.NET，它是用來向數據庫提交sql語句的一堆類。這里連接的是Sql Server 2008數據庫，其他數據庫用法差不多，就是調用的類名不一樣2015-11-11
本文主要介紹了c# winform多線程死循環(huán)踩坑,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2023-12-12
這篇文章主要介紹了C# 循環(huán)判斷會進來幾次的實現代碼，代碼中就一個循環(huán)，循環(huán)的判斷是從一個函數獲取值,需要的朋友可以參考下2018-06-06
一個簡單的例子，比如說貓叫，老鼠跑，主人被驚醒,在不知道觀察者模式之前，我們的代碼可能是這樣的2012-10-10
c#下將.cs文件編譯成dll...2007-07-07
c#獲取本機的IP地址的代碼，需要的朋友可以參考一下2013-03-03
這篇文章主要介紹了泛型去掉字段重復數據的方法,大家參考使用吧2014-01-01