數(shù)據(jù)結(jié)構(gòu)：優(yōu)先隊列--堆

堆是1棵被完全填滿的2叉樹。底層可以例外。同樣成為完全2叉樹。

由于完全2叉樹很有規(guī)律，所以可以用1個數(shù)組表示而不需要使用鏈。

對任1個位置i上的元素，左兒子在2i上，右兒子在2i+1上。其父親在i/2上。

堆的某個結(jié)點，必須必它的子孫結(jié)點都小，所以堆是完全2叉樹，但是完全2叉樹不1定是堆。

//
//  Heap.h
//  HelloWorld
//  csdn blog：http://blog.csdn.net/u012175089
//  Created by feiyin001 on 17/1/10.
//  Copyright (c) 2017年 FableGame. All rights reserved.
//

#ifndef __HelloWorld__Heap__
#define __HelloWorld__Heap__
#include "Vector.h"

namespace Fable {
    template<typename Comparable>
    class BinaryHeap
    {
    public:
        //默許構(gòu)造函數(shù)
        explicit BinaryHeap(int capacity = 100):array(capacity){}
        //用已有的數(shù)組創(chuàng)建堆的構(gòu)造函數(shù)
        explicit BinaryHeap(const Vector<Comparable>& items)
        :array(items.size() + 10), currentSize(items.size())
        {
            //插入數(shù)據(jù)
            for (int i = 0; i < items.size(); i++)
            {
                array[i+1] = items[i];
            }
            //構(gòu)建堆
            buildHeap();
        }
        
        bool isEmpty()const
        {
            return currentSize == 0;
        }
        const Comparable& findMin()const
        {
            return array[1];
        }
        //插入數(shù)據(jù)
        void insert(const Comparable& x)
        {
            //如果容量不夠，就擴大1倍
            if (currentSize == array.size() - 1)
            {
                array.resize(array.size() * 2);
            }
            //下表號是從1開始的，所以是自增以后
            int hole = ++currentSize;
            for (; hole > 1&& x < array[hole/2]; hole /= 2)//比父結(jié)點小，交換，交換到根結(jié)點，也就是1的時候，就要停止了
            {
                array[hole] = array[hole/2];//把父結(jié)點往下移動
            }
            array[hole] = x;//x放在最新的位置上面
        }
        //刪除最小的1項
        void deleteMin()
        {
            if (isEmpty()) {
                throw "UnderflowException";//拋異常
            }
            array[1] = array[currentSize--];
            percolateDown(1);//進行下慮
        }
        //刪除最小的1項
        void deleteMin(Comparable& minItem)
        {
            if (isEmpty()) {
                throw "UnderflowException";//拋異常
            }
            minItem = array[1];
            array[1] = array[currentSize--];
            percolateDown(1);//進行下慮
        }
        void makeEmpty()
        {
            currentSize = 0;
        }
    private:
        int currentSize;
        Vector<Comparable> array;
        //構(gòu)建堆，主要利用在亂序的數(shù)據(jù)上面
        void buildHeap()
        {
            //大于currentSize/2的結(jié)點已在最底層，是不需要下濾的了。
            for (int i = currentSize/2; i>0; i--)//必須從下往上進行下慮
            {
                percolateDown(i);
            }
        }
        //下慮，將不合適的對象往下沉到合適的位置，O(logN)
        void percolateDown( int hole )
        {
            int child;
            Comparable tmp = array[hole];//當(dāng)前位置的對象
            for (; hole * 2 <= currentSize; hole = child)//當(dāng)前位置如果沒有子節(jié)點了，就終止循環(huán)，循環(huán)過后檢測孩子的位置的數(shù)據(jù)
            {
                child = hole * 2;//第1個孩子
                if (child != currentSize && array[child + 1] < array[child])
                {
                    child++;//第2個孩子比第1個孩子小，選中小的1個
                }
                if (array[child] < tmp)//孩子比對象小
                {
                    array[hole] = array[child];//把孩子往上移
                }
                else
                {
                    break;//比最小的孩子還小，這個位置是適合的了。
                }
            }
            array[hole] = tmp;//把對象放到孩子的位置。
        }
    };
}

#endif /* defined(__HelloWorld__Heap__) */

這是1般意義長的堆，由于用得最多。其實還有最大堆，根比子節(jié)點大。

STL實現(xiàn)了1個最大堆，而不是最小堆。

下面的堆概念平時比較少用到，以后要用到再研究了。

查找兒子和父親的乘法和除法都和因子d有關(guān)。

除非d是2的冪，否則將不能通過2進制移位來實現(xiàn)觸發(fā)而致使運行時間急劇增加。

除不能履行find操作外，兩個堆合2為1是很困難的操作。

左式堆：以堆的情勢構(gòu)建，父節(jié)點比子節(jié)點小，不同的是，不是完全2叉樹。

零路徑長（null path length）npl(X)定義為從X結(jié)點到1個不具有兩個兒子的節(jié)點的最短路徑的長。

因此具有0或1個兒子的結(jié)點的npl為0.npl(NULL) == ⑴

斜堆（skew heap）是左式堆的自調(diào)理情勢。

2項隊列：1個2項隊列不是1棵堆序的樹，而是堆序的樹的集合，稱為森林。

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進行捐贈