優(yōu)先隊(duì)列

許多應(yīng)用程序都需要處理有序的元素，但不一定要求它們?nèi)坑行颍蚴遣灰欢ㄒ淮尉蛯⑺鼈兣判颉：芏嗲闆r下是收集一些元素，處理當(dāng)前鍵值最大的元素，然后再收集更多的元素，再處理當(dāng)前鍵值最大的元素。這種情況下，需要的數(shù)據(jù)結(jié)構(gòu)支持兩種操作：刪除最大的元素和插入元素。這種數(shù)據(jù)結(jié)構(gòu)類型叫優(yōu)先隊(duì)列。

這里，優(yōu)先隊(duì)列基于二叉堆數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，用數(shù)組保存元素并按照一定條件排序，以實(shí)現(xiàn)對數(shù)級別的刪除和插入操作。

1.API

優(yōu)先隊(duì)列是一種抽象數(shù)據(jù)類型，它表示了一組值和對這些值的操作，抽象層使應(yīng)用和實(shí)現(xiàn)隔離開來。

2.初級實(shí)現(xiàn)

• 1.無序數(shù)組實(shí)現(xiàn)
  優(yōu)先隊(duì)列的 insert 方法和下壓棧的 push 方法一樣。刪除最大元素時(shí)，遍歷數(shù)組找出最大元素，和邊界元素交換。
• 2.有序數(shù)組實(shí)現(xiàn)
  插入元素時(shí)，將較大的元素向右移一格（和插入排序一樣）。這樣刪除時(shí)，就可以直接 pop。

使用鏈接也是一樣的邏輯。

這些實(shí)現(xiàn)總有一種操作需要線性級別的時(shí)間復(fù)雜度。使用二叉堆可以保證操作在對數(shù)級別的時(shí)間完成。

3.堆的定義

數(shù)據(jù)結(jié)構(gòu)二叉堆可以很好地實(shí)現(xiàn)優(yōu)先隊(duì)列地基本操作。在二叉堆數(shù)組中，每個(gè)元素都要保證大于等于另兩個(gè)特定位置地元素。同樣，這兩個(gè)位置地元素又至少要大于等于數(shù)組中另外兩個(gè)元素，以此類推。用二叉樹表示：

當(dāng)一棵二叉樹的每個(gè)結(jié)點(diǎn)都大于等于它的兩個(gè)子節(jié)點(diǎn)時(shí)，它被成為堆有序。從任意結(jié)點(diǎn)向上，都能得到一列非遞減的元素；從任意結(jié)點(diǎn)向下，都能得到一列非遞增的元素。根結(jié)點(diǎn)是堆有序的二叉樹中最大的結(jié)點(diǎn)。

二叉堆表示法

這里使用完全二叉樹表示：將二叉樹的結(jié)點(diǎn)按照層級順序（從上到下，從左往右）放入數(shù)組中，不使用數(shù)組的第一個(gè)位置（為了方便計(jì)算），根結(jié)點(diǎn)在位置 1 ，它的子結(jié)點(diǎn)在位置 2 和 3，子結(jié)點(diǎn)的子結(jié)點(diǎn)分別在位置 4，5，6，7，一次類推。

在一個(gè)二叉堆中，位置 k 的結(jié)點(diǎn)的父節(jié)點(diǎn)位置在 k/2，而它的兩個(gè)子結(jié)點(diǎn)在 2k 和 2k + 1。可以通過計(jì)算數(shù)組的索引而不是指針就可以在樹中上下移動。

一棵大小為 N 的完全二叉樹的高度為 lgN。

4.堆的算法

用長度為 N+1 的私有數(shù)組 pq[ ] 表示一個(gè)大小為 N 的堆。

堆在進(jìn)行插入或刪除操作時(shí)，會打破堆的狀態(tài)，需要遍歷堆并按照要求將堆的狀態(tài)恢復(fù)。這個(gè)過程稱為 堆的有序化。

堆的有序化分為兩種情況：當(dāng)某個(gè)結(jié)點(diǎn)的優(yōu)先級上升（或在堆底加入一個(gè)新的元素）時(shí)，需要由下至上恢復(fù)堆的順序；當(dāng)某個(gè)結(jié)點(diǎn)的優(yōu)先級下降（例如將根節(jié)點(diǎn)替換為一個(gè)較小的元素），需要由上至下恢復(fù)堆的順序。

上浮（由下至上的堆的有序化）

當(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)和同級的另一個(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í)，可以通過將它和它的兩個(gè)子結(jié)點(diǎn)較大者交換來恢復(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;
        }
    }

上述算法對優(yōu)先隊(duì)列的實(shí)現(xiàn)能夠保證插入和刪除最大元素這兩個(gè)操作的用時(shí)和隊(duì)列的大小成對數(shù)關(guān)系。這里省略了動態(tài)調(diào)整數(shù)組大小的代碼，可以參考下壓棧。

對于一個(gè)含有 N 個(gè)元素的基于堆的優(yōu)先隊(duì)列，插入元素操作只需要不超過（lgN + 1）次比較，因?yàn)?N 可能不是 2 的冪。刪除最大元素的操作需要不超過 2lgN次比較（兩個(gè)子結(jié)點(diǎn)的比較和父結(jié)點(diǎn)與較大子節(jié)點(diǎn)的比較）。

對于需要大量混雜插入和刪除最大元素的操作，優(yōu)先隊(duì)列很適合。

改進(jìn)

• 1.多叉堆
  基于數(shù)組表示的完全三叉樹：對于數(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ù)組大小
  使用動態(tài)數(shù)組，可以構(gòu)造一個(gè)無需關(guān)注隊(duì)列大小的優(yōu)先隊(duì)列。可以參考下壓棧。
• 3.索引優(yōu)先隊(duì)列
  在許多應(yīng)用程序中，允許客戶端引用優(yōu)先級隊(duì)列中已經(jīng)存在的項(xiàng)目是有意義的。一種簡單的方法是將唯一的整數(shù)索引與每個(gè)項(xiàng)目相關(guān)聯(lián)。

堆排序

我們可以把任意優(yōu)先隊(duì)列變成一種排序方法：先將所有元素插入一個(gè)查找最小元素的優(yōu)先隊(duì)列，再重復(fù)調(diào)用刪除操作刪除最小元素來將它們按順序刪除。這種排序成為堆排序。

堆排序的第一步是堆的構(gòu)造，第二步是下沉排序階段。

1.堆的構(gòu)造

簡單的方法是利用前面優(yōu)先隊(duì)列插入元素的方法，從左到右遍歷數(shù)組調(diào)用Swim 方法（由上算法所需時(shí)間和 N logN 成正比）。一個(gè)更聰明高效的方法是，從右（中間位置）到左調(diào)用Sink 方法，只需遍歷一半數(shù)組，因?yàn)榱硪话胧谴笮?1 的堆。這種方法只需少于 2N 次比較和 少于 N 次交換。（堆的構(gòu)造過程中處理的堆都比較小。例如，要構(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 來自堆的構(gòu)造，2N lgN 是每次下沉操作最多需要 2lgN 次比較。

先下沉后上浮

在排序過程中，大多數(shù)重新插入堆中的項(xiàng)目都會一直到達(dá)底部。因此，通過避免檢查元素是否已到達(dá)其位置，可以簡單地提升兩個(gè)子結(jié)點(diǎn)中的較大者直到到達(dá)底部，然后上浮到適當(dāng)位置，從而節(jié)省時(shí)間。這個(gè)方法將比較數(shù)減少了2倍，但需要額外的簿空間。只有當(dāng)比較操作代價(jià)較高時(shí)可以使用這種方法。（例如將字符串或其他鍵值較長類型的元素排序）。

堆排序是能夠同時(shí)最優(yōu)利用空間和時(shí)間的方法，在最壞情況下也能保證 ~2N lgN 次比較和恒定的額外空間。當(dāng)空間緊張時(shí)，可以使用堆排序。但堆排序無法利用緩存。因?yàn)樗臄?shù)組元素很少喝相鄰的其他元素比較，因此緩存未命中的次數(shù)要遠(yuǎn)高于大多數(shù)比較都在相鄰元素之間進(jìn)行的算法。