淺析STL算法中的堆排序

堆結(jié)構(gòu)簡(jiǎn)述

    了解過(guò)數(shù)據(jù)結(jié)構(gòu)的人，應(yīng)該對(duì)堆結(jié)構(gòu)不陌生，堆的底層是使用數(shù)組來(lái)實(shí)現(xiàn)的，但卻保持了二叉樹(shù)的特性。堆分為兩種，最大堆和最小堆，以最大堆為例，最大堆保持了根結(jié)點(diǎn)大于兩個(gè)左右兩個(gè)孩子，同時(shí)所有子樹(shù)一次類推。由于堆底層是數(shù)組結(jié)構(gòu)，這里從跟結(jié)點(diǎn)開(kāi)始，按照層序依次走到最后一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)下標(biāo)分貝為0~N-1。結(jié)構(gòu)如下圖：

    上圖中，紫色表示的是該元素在數(shù)組中的下標(biāo)，可以看到，每個(gè)結(jié)點(diǎn)的值總是大于它的左右孩子，這里并沒(méi)有規(guī)定左右孩子的大小關(guān)系，也沒(méi)有規(guī)定不是同一棵樹(shù)之間結(jié)點(diǎn)的大小關(guān)系。這就是最大堆。同時(shí)這里可以注意到，如果是大堆，根節(jié)點(diǎn)一定是樹(shù)中最大的結(jié)點(diǎn)，同樣，如果是小堆，根節(jié)點(diǎn)一定是樹(shù)中最小的結(jié)點(diǎn)。

    堆結(jié)構(gòu)在排序領(lǐng)域，占據(jù)著一定的低位，但是STL中并沒(méi)有直接給出堆結(jié)構(gòu)，而是把堆的相關(guān)算法，寫(xiě)在了 algorithm 里面。在這里我不會(huì)過(guò)多的去模擬實(shí)現(xiàn)一個(gè)堆，今天要說(shuō)的是關(guān)于STL中給出的堆算法如何使用。

algorithm 中的堆算法

    在STL中，關(guān)于堆，給出了一下幾種算法。

    ★make_heap    

    ★push_heap

    ★pop_heap

    ★sort_heap

    這里，首先給出一個(gè)利用STL中堆算法的實(shí)例

#include <algorithm>
#include <vector>
void test()
{
    int arr[] = {1,2,3,4,5,6,7};
    vector<int> vec(arr, arr+7);         // 左開(kāi)右閉類型
    make_heap(vec.begin(), vec.end());   // 默認(rèn)建大堆
    pop_heap(v1.begin(), v1.end());      
    v1.pop_back();                       
    sort_heap(vec.begin(), vec.end());   // 堆排序
    for(size_t i = 0; i < vec.size(); i++)
        cout<<vec[i]<<" ";
    cout<<endl;
}

    上面代碼，首先用一個(gè)數(shù)組構(gòu)建了一個(gè)向量，之后對(duì)向量vec建堆，pop出調(diào)整之后的向量中第一個(gè)元素，并進(jìn)行調(diào)整，然后進(jìn)行堆排序，最后將結(jié)果打印出來(lái)，打印結(jié)果如下：

    看完了heap算法的基本使用，現(xiàn)在，我們了解一下，STL中是如何提供這些算法接口的。

1、make_heap

template <class RandomAccessIterator>
  void make_heap (RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>
  void make_heap (RandomAccessIterator first, RandomAccessIterator last,
                  Compare comp );

    前面提到過(guò)，堆分為大堆和小堆，我們建立堆的時(shí)候就需要確定，但剛剛例子中，我們并沒(méi)有去指定大小堆。STL中規(guī)定，沒(méi)有指定的話，默認(rèn)大堆結(jié)構(gòu)。從上面關(guān)于make_heap的兩套接口可以看到，第一種是默認(rèn)的，沒(méi)有提供指定大小堆的接口，第二種這里有實(shí)現(xiàn)。我們可通過(guò)仿函數(shù)的結(jié)構(gòu)，實(shí)現(xiàn)這里的傳參。

    對(duì)剛剛給出的例子，我們現(xiàn)在可以解釋另外一個(gè)問(wèn)題，為什么我們要進(jìn)行堆排序，首先要構(gòu)建vector呢？因?yàn)槎训牡讓訉?shí)現(xiàn)就是通過(guò)數(shù)組的形式，而vector是堆數(shù)組的高級(jí)封裝，這些庫(kù)中實(shí)現(xiàn)好的容器給出了很多實(shí)用的接口和迭代器，使用起來(lái)的確可以方便不少。make_heap給出的接口中，前兩個(gè)是任意類型的迭代器（當(dāng)然，這里也可以直接傳遞數(shù)組的指針），不論是make_heap還是其他三個(gè)函數(shù)，這里的迭代器區(qū)間總是左閉右開(kāi)的，這是個(gè)需要注意的地方。

    接下來(lái)我們來(lái)介紹仿函數(shù)這里的實(shí)現(xiàn)。還是上面的例子，如何讓上面剪子一個(gè)最小堆呢？

//仿函數(shù)結(jié)構(gòu)：

struct Compare
{
   bool operator()(int num1, int num2)
	           {
		      return num1 > num2;
	   }
};

// 建堆時(shí)，參數(shù)傳遞改為

make_heap(vec.begin(), vec.end() , Compare());   // 建小堆

    注意，上面我寫(xiě)的是num1 > num2，這樣建出來(lái)頂點(diǎn)是小堆。關(guān)于make_heap就說(shuō)到這里。

2、push_heap 與 pop_heap 

    push表示的是向vector中插入一個(gè)元素，但這里它并不是直接插入元素，準(zhǔn)確的說(shuō)，它的功能只是做調(diào)整，在push_heap之前，首先需要調(diào)用vec.push_back(x)，向vector尾部插入一個(gè)元素，然后在調(diào)用push_heap函數(shù)進(jìn)行調(diào)整，使得整個(gè)樹(shù)重新滿足堆結(jié)構(gòu)。

    pop_heap與push_heap類似，同樣沒(méi)有直接改變vector中元素個(gè)數(shù)的能力。對(duì)于堆而言，pop要做的是將vector的第一個(gè)元素扔出去，為了不直接破壞樹(shù)的結(jié)構(gòu)，這里先調(diào)用pop_heap函數(shù)，將堆中的最大值或最小值放到vector的尾部，同時(shí)進(jìn)行一次調(diào)整，使得堆結(jié)構(gòu)依然成立，然后調(diào)用vec.pop+back()函數(shù)，將最后一個(gè)元素從vector中剔除。

    這就是插入和刪除的整個(gè)過(guò)程。

3、sort_heap

    顧名思義，sort_heap就是進(jìn)行堆排序的意思，對(duì)堆結(jié)構(gòu)進(jìn)行排序，得到的結(jié)果就是vector中的元素變得有序。這里，構(gòu)建大堆，排序結(jié)果是升序的，構(gòu)建小堆，得到的排序結(jié)果是降序的。

    上面就是關(guān)于堆排序的基本算法，關(guān)于C++11新引入的兩個(gè)函數(shù)，這里不做討論。

    關(guān)于STL中的堆結(jié)構(gòu)，這里有幾點(diǎn)還是需要注意的：

    1、因?yàn)槎呀Y(jié)構(gòu)，是建立在vector上的結(jié)構(gòu)，所以如果要進(jìn)行堆排序，整個(gè)過(guò)程中至少一次建堆（make_heap）的過(guò)程。

    2、當(dāng)建堆完成之后，如果再向vector中插入元素，需要調(diào)用 push_heap(v1.begin(), v1.end()) 進(jìn)行一次向上調(diào)整；如果從vector中Pop出一個(gè)元素，需要調(diào)用 pop_heap(v1.begin(), v1.end()) 進(jìn)行一次向下調(diào)整。

    如果沒(méi)有調(diào)整，當(dāng)調(diào)用 sort_heap(v1.begin(), v1.end()) 函數(shù)的過(guò)程中，會(huì)出現(xiàn)由于堆不合法引起的斷言錯(cuò)誤。

    3、不可以讓vector多次尾插，之后再多次向上調(diào)整，會(huì)造成堆混亂，排序時(shí)也會(huì)出現(xiàn)斷言錯(cuò)誤。當(dāng)然，多次插入或刪除之后，可以再次進(jìn)行重新建堆，只不過(guò)消耗的時(shí)間代價(jià)會(huì)比較大。

堆結(jié)構(gòu)實(shí)際應(yīng)用

接下來(lái)，看一道面試題：

CVTE：統(tǒng)計(jì)公司員工最喜歡吃的前K種水果

   有過(guò)上面的基礎(chǔ)，我這里直接給出demo

#include <algorithm>
#include <map>
#include <string>
#include <vector>

struct Min
{
            bool operator()(pair<string, int> p1, pair<string, int> p2)
            {
                        return p1.second > p2.second;
            }
};
void HeapSort()
{
            vector<string> v1 = { "蘋果", "香蕉", "蘋果"
                        , "蘋果", "蘋果", "香蕉"
                        , "蘋果", "獼猴桃", "草莓" };
            map<string, int> fruit;
            
            //用map統(tǒng)計(jì)次數(shù)
            for (size_t i = 0; i < v1.size(); i++)
            {
                        fruit[v1[i]]++;
            }

            // 用heap排序
            vector<pair<string, int>> vec;
            map<string, int>::iterator it = fruit.begin();
            //while (it != fruit.end())
            //{
            //         vec.push_back(pair<string, int>(it->first, it->second));
            //         it++;
            //}
            vec.insert(vec.begin(), fruit.begin(), fruit.end());
            make_heap(vec.begin(), vec.end(), Min());
            sort_heap(vec.begin(), vec.end(), Min());
            int K = 3;
            for (size_t i = 0; (i < K) && (i < vec.size()); i++)
            {
                        cout << vec[i].first <<"--"<<vec[i].second<< endl;
            }
}
int main()
{
            HeapSort();
            system("pause");
            return 0;
}

    堆排序是數(shù)據(jù)結(jié)構(gòu)中一塊很重要的內(nèi)容，如果是在實(shí)際開(kāi)發(fā)中，更加推薦的是熟悉STL中給出的算法，正如上文講到的內(nèi)容。如果是對(duì)于初學(xué)者，這里還是推薦對(duì)堆結(jié)構(gòu)和算法的底層實(shí)現(xiàn)有一個(gè)更加深刻的認(rèn)識(shí)，對(duì)于堆的調(diào)整算法，不可否認(rèn)，是數(shù)據(jù)結(jié)構(gòu)中較為重要的一部分。下一次，會(huì)對(duì)堆結(jié)構(gòu)進(jìn)行模擬實(shí)現(xiàn)，更加深入地了解底層結(jié)構(gòu)。