堆是什么？剛接觸到這個(gè)概念估計(jì)都摸不著頭腦，不知道堆是什么樣個(gè)東西。簡(jiǎn)單介紹下，

主要從事網(wǎng)頁(yè)設(shè)計(jì)、PC網(wǎng)站建設(shè)（電腦版網(wǎng)站建設(shè)）、wap網(wǎng)站建設(shè)（手機(jī)版網(wǎng)站建設(shè)）、響應(yīng)式網(wǎng)站建設(shè)、程序開(kāi)發(fā)、微網(wǎng)站、小程序設(shè)計(jì)等，憑借多年來(lái)在互聯(lián)網(wǎng)的打拼，我們?cè)诨ヂ?lián)網(wǎng)網(wǎng)站建設(shè)行業(yè)積累了豐富的成都網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)、網(wǎng)絡(luò)營(yíng)銷經(jīng)驗(yàn)，集策劃、開(kāi)發(fā)、設(shè)計(jì)、營(yíng)銷、管理等多方位專業(yè)化運(yùn)作于一體，具備承接不同規(guī)模與類型的建設(shè)項(xiàng)目的能力。

堆數(shù)據(jù)結(jié)構(gòu)是一種數(shù)組對(duì)象，它可以被視為一棵完全二叉樹(shù)結(jié)構(gòu)。

堆結(jié)構(gòu)的二叉樹(shù)存儲(chǔ)有兩種情況：

  (1).最大堆：每個(gè)父節(jié)點(diǎn)的都大于孩子節(jié)點(diǎn)。

  (2).最小堆：每個(gè)父節(jié)點(diǎn)的都小于孩子節(jié)點(diǎn)。

舉個(gè)例子可能好理解些，看下面：

int a[] = {10,11,13,12,16,18,15,17,14,19};

  熟悉了它的結(jié)構(gòu)，給解釋下怎么來(lái)構(gòu)建這個(gè)堆。

對(duì)于他的實(shí)現(xiàn)，我們直接可以借用vector作為成員，因?yàn)槭褂玫降臄?shù)組要實(shí)現(xiàn)增刪查改，增容是肯定會(huì)用到的，將傳過(guò)來(lái)的數(shù)組全部push_back到vector中去，然后從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始向下調(diào)整，知道最后調(diào)整玩根結(jié)點(diǎn)，就完成了堆的構(gòu)成。

 

  那么什么叫做向下調(diào)整了？

向下調(diào)整就是從第一個(gè)非葉子節(jié)點(diǎn)作為一顆子樹(shù)開(kāi)始調(diào)整，將大的數(shù)據(jù)放大父節(jié)點(diǎn)上，依次調(diào)整，直至調(diào)整到根節(jié)點(diǎn)為止

#include <vector>
template <class T>
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 _AdjustDown(size_t parent)
    {
        size_t child = 2 * parent + 1;

        while (child < _a.size())
        {
            //找出孩子中的最大孩子
            if (child + 1 < _a.size() && _a[child] < _a[child + 1])
            {
                ++child;
            }
            //把
            if (_a[parent] < _a[child])
            {
                swap(_a[parent], _a[child]);
                parent = child;
                child = child * 2 + 1;
            }
            else
            {
                break;
            }
        }

  下面再重點(diǎn)介紹下pop函數(shù)的寫(xiě)法，pop函數(shù)就相當(dāng)于將根節(jié)點(diǎn)刪除了，我們轉(zhuǎn)換下思路，將根節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)交換，然后就需要寫(xiě)一個(gè)向上調(diào)整的函數(shù)就行了。向上調(diào)整的思路：由于交換后根節(jié)點(diǎn)變成了最后一個(gè)節(jié)點(diǎn)的值，比原來(lái)根節(jié)點(diǎn)的左右小，所以需要用左右節(jié)點(diǎn)中的大值將這個(gè)小值換下來(lái)。

void pop()
    {
        size_t size = _a.size();
        assert(size > 0);
        swap(_a[0], _a[size - 1]);
        _a.pop_back();
        size = _a.size();
        _AdjustDown(0);
    }
    
    void _AdjustUp(int child)
    {
        int parent = (child - 1) / 2;

        while (parent >= 0)
        {
            //找出孩子中的最大孩子
            if (_a[child] > _a[parent])
            {
                swap(_a[child], _a[parent]);
                child = parent;
                parent = (child - 1) / 2;
            }
            else
            {
                break;
            }
        }

    }

其他函數(shù)：

void push(const T& x)
    {
        _a.push_back(x);
        _AdjustUp(_a.size() -1);
    }
    
    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;
    }

分享名稱：【數(shù)據(jù)結(jié)構(gòu)】堆的實(shí)現(xiàn)以及簡(jiǎn)單的函數(shù)
分享鏈接：http://chinadenli.net/article14/pigpde.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供域名注冊(cè)、Google、自適應(yīng)網(wǎng)站、商城網(wǎng)站、做網(wǎng)站、品牌網(wǎng)站設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)