一、用模版實(shí)現(xiàn)大小堆

作為一家“創(chuàng)意+整合+營銷”的成都網(wǎng)站建設(shè)機(jī)構(gòu)，我們?cè)跇I(yè)內(nèi)良好的客戶口碑。創(chuàng)新互聯(lián)建站提供從前期的網(wǎng)站品牌分析策劃、網(wǎng)站設(shè)計(jì)、做網(wǎng)站、網(wǎng)站設(shè)計(jì)、創(chuàng)意表現(xiàn)、網(wǎng)頁制作、系統(tǒng)開發(fā)以及后續(xù)網(wǎng)站營銷運(yùn)營等一系列服務(wù)，幫助企業(yè)打造創(chuàng)新的互聯(lián)網(wǎng)品牌經(jīng)營模式與有效的網(wǎng)絡(luò)營銷方法,創(chuàng)造更大的價(jià)值。

   如果不用模版的話，寫大小堆，就需要分別實(shí)現(xiàn)兩次，但是應(yīng)用模版的話問題就簡(jiǎn)單多了，我們只需要實(shí)現(xiàn)兩個(gè)仿函數(shù)，Greater和Less就行了，仿函數(shù)就是用類實(shí)現(xiàn)一個(gè)()的重載就實(shí)現(xiàn)了仿函數(shù)。這個(gè)看下代碼就能理解了。再設(shè)計(jì)參數(shù)的時(shí)候，需要把模版設(shè)計(jì)成模版的模版參數(shù)，因?yàn)橐獙?shí)現(xiàn)大小堆嘛！當(dāng)我們實(shí)現(xiàn)好一個(gè)大堆或者小隊(duì)的邏輯后只需要用模版接收的Greater或Less類定義一個(gè)變量，就能實(shí)現(xiàn)通用功能了。

template
struct Less
{
    bool operator()(const T& l, const T& r)
    {
        return l < r;
    }
};

template
struct Greater
{
    bool operator()(const T& l, const T& r)
    {
        return l>r;
    }
};

template  class compare = less>
class Heap
{
public:
    Heap()
    {}

    Heap(T* a,size_t size)
    {
        size_t index = 0;
        while (index < size)
        {
            _a.push_back(a[index]);
            index++;
        }

        for (int i = (_a.size() - 2) / 2; i >= 0; i--)
            _AdjustDown(i);
    }

    void push(const T& x)
    {
        _a.push_back(x);
        _AdjustUp(_a.size() -1);
    }

    void pop()
    {
        size_t size = _a.size();
        assert(size > 0);
        swap(_a[0], _a[size - 1]);
        _a.pop_back();
        size = _a.size();
        _AdjustDown(0);
    }

    size_t top()
    {
        assert(!_a.empty());

        return _a[0];
    }

    bool empty()
    {
        return _a.size() == 0;
    }

    size_t Size()
    {
        return _a.size();
    }

    void Print()
    {
        for (int i = 0; i < _a.size(); i++)
        {
            cout << _a[i] << " ";
        }
        cout << endl;
    }

protected:
    void _AdjustUp(int child)
    {
        int parent = (child - 1) / 2;
        compare com;  //如果是大堆傳過來就是用大堆的邏輯，小堆就實(shí)現(xiàn)小堆的邏輯
        while (child > 0)
        {
            //找出孩子中的大孩子
            if (com(_a[child] , _a[parent]))
            {
                swap(_a[child], _a[parent]);
                child = parent;
                parent = (child - 1) / 2;
            }
            else
            {
                break;
            }
        }

    }

    void _AdjustDown(size_t parent)
    {
        size_t child = 2 * parent + 1;
        compare com; //如果是大堆傳過來就是用大堆的邏輯，小堆就實(shí)現(xiàn)小堆的邏輯
        while (child < _a.size())
        {
            //找出孩子中的大孩子
            if (child + 1 < _a.size() && com(_a[child+1] ,_a[child]))
            {
                ++child;
            }
            //把
            if (com(_a[child] , _a[parent]))
            {
                swap(_a[parent], _a[child]);
                parent = child;
                child = child * 2 + 1;
            }
            else
            {
                break;
            }
        }

    }
protected:
    vector _a;
};

   二、用模版實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列

前面實(shí)現(xiàn)了大小堆，這里我們可以使用適配器，直接調(diào)用大小堆，來實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列。

template class compare = Less>
class priorityQueue
{
private:
    Heap _hp; 
public:
    void push(const T& x)
    {
        _hp.push(x);
    }

    void pop()
    {
        _hp.pop();
    }

    T& Top()
    {
        return _hp.top();
    }

    void Print()
    {
        _hp.Print();
    }

};

   三、堆排序的實(shí)現(xiàn)

   堆排序的實(shí)現(xiàn)簡(jiǎn)單思路，(升序)先構(gòu)造出來一個(gè)大堆，調(diào)整堆后，將堆頭和最后一個(gè)數(shù)據(jù)交換，大值就換到了數(shù)組的最后，然后在調(diào)整堆，但是size需要減少1，因?yàn)榇蟮囊呀?jīng)調(diào)整到最后，如果再加上它調(diào)整又會(huì)回到堆頭。

int*& HeapSort(int* a, size_t size)
{
    for (int i = (size - 2) / 2; i >= 0; i--)
    {
        _AdjustDown(a, size, i);
    }

    for (int i = 0; i < size; i++)
    {
        swap(a[0], a[size - i - 1]);
        _AdjustDown(a, size - i - 1, 0);
    }

    return a;
}

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

文章名稱：【數(shù)據(jù)結(jié)構(gòu)】用模版實(shí)現(xiàn)大小堆、實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列，以及堆排序-創(chuàng)新互聯(lián)
當(dāng)前路徑：http://weahome.cn/article/icoss.html