• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            The Fourth Dimension Space

            枯葉北風寒,忽然年以殘,念往昔,語默心酸。二十光陰無一物,韶光賤,寐難安; 不畏形影單,道途阻且慢,哪曲折,如渡飛湍。斬浪劈波酬壯志,同把酒,共言歡! -如夢令

            最小堆類

            #include<iostream>
            #include
            <cmath>
            #include
            <algorithm>
            using namespace std;


            template
            <class T>
            class MinHeap
            {
            private:
                T 
            *heap;
                
            int CurrentSize;
                
            int MaxSize;
                
            void FilterDown(const int start,const int end);
                
            void FilterUp(int start);
            public:
                MinHeap(
            int n);
                MinHeap();
                
            ~MinHeap(){delete []heap;}
                
            bool Insert(const T &x);
                T RemoveMin();
                T GetMin();
                
            bool IsEmpty() const{return CurrentSize==0;}
                
            bool IsFull() const{return CurrentSize==MaxSize;}
                
            void Clear(){CurrentSize=0;}
            }
            ;


            template
            <class T>
            MinHeap
            <T>::MinHeap()
            {

                MaxSize
            =1000;
                heap
            =new T[MaxSize];
                CurrentSize
            =0;

            }

            template
            <class T>
            MinHeap
            <T>::MinHeap(int n)
            {

                MaxSize
            =n;
                heap
            =new T[MaxSize];
                CurrentSize
            =0;
            }


            template
            <class T>
            void MinHeap<T>::FilterDown(const int start,const int end)
            {

                
            int i=start,j=2*i+1;
                T temp
            =heap[i];
                
            while(j<=end)
                
            {

                    
            if(j<end&&heap[j]>heap[j+1])
                        j
            ++;
                    
            if(temp<=heap[j])
                        
            break;
                    
            else 
                    
            {

                        heap[i]
            =heap[j];i=j;j=2*j+1;
                    }

                }

                heap[i]
            =temp;
            }



            template
            <class T>
            bool MinHeap<T>::Insert(const T &x)
            {

                
            if(CurrentSize==MaxSize)
                    
            return false;
                heap[CurrentSize]
            =x;
                FilterUp(CurrentSize);
                CurrentSize
            ++;
                
            return true;
            }



            template
            <class T>
            void MinHeap<T>::FilterUp(int start)
            {

                
            int j=start,i=(j-1)/2;
                T temp
            =heap[j];
                
            while(j>0)
                
            {

                    
            if(heap[i]<=temp)break;
                    
            else
                        heap[j]
            =heap[i];j=i;i=(i-1)/2;

                }

                heap[j]
            =temp;
            }




            template
            <class T>
            T MinHeap
            <T>::RemoveMin( )
            {
                T x
            =heap[0];
                heap[
            0]=heap[CurrentSize-1];
                CurrentSize
            --;
                FilterDown(
            0,CurrentSize-1);
                
            return x;
            }


            template
            <class T>
            T MinHeap
            <T>::GetMin()
            {

                
            return heap[0];
            }



            int main ()
            {
                MinHeap
            <int> test(8);
                
            int k;
                
            bool tem;
                
            for(k=1;k<=10;k++)
                
            {

                    tem
            =test.Insert(10-k);
                }

                tem
            =test.IsEmpty();
                tem
            =test.IsFull();
                
            for(k=1;k<=5;k++)
                    test.RemoveMin();
                
            return 0;

            }


            一個自實現的優先隊列 最小堆。


            #include<iostream>
            #include
            <cmath>
            #include
            <algorithm>
            using namespace std;


            template
            <class T>
            class MinHeap
            {
            public:
                T 
            *heap;
                
            int CurrentSize;
                
            int MaxSize;
                
            void FilterDown(const int start,const int end);
                
            void FilterUp(int start);
            public:
                MinHeap(
            int n);
                
            ~MinHeap(){delete []heap;}
                
            bool Insert(const T &x);
                T RemoveMin();
                T GetMin();
            }
            ;

            template
            <class T>
            MinHeap
            <T>::MinHeap(int n)
            {

                MaxSize
            =n;
                heap
            =new T[MaxSize];
                CurrentSize
            =0;
            }


            template
            <class T>
            void MinHeap<T>::FilterDown(const int start,const int end)
            {

                
            int i=start,j=2*i+1;
                T temp
            =heap[i];
                
            while(j<=end)
                
            {

                    
            if(j<end&&heap[j+1]<heap[j])
                        j
            ++;
                    
            if(temp<heap[j])
                        
            break;
                    
            else 
                        heap[i]
            =heap[j];i=j;j=2*j+1;
                }

                heap[i]
            =temp;
            }



            template
            <class T>
            bool MinHeap<T>::Insert(const T &x)
            {

                
            if(CurrentSize==MaxSize)
                    
            return false;
                heap[CurrentSize]
            =x;
                FilterUp(CurrentSize);
                CurrentSize
            ++;
                
            return true;
            }



            template
            <class T>
            void MinHeap<T>::FilterUp(int start)
            {

                
            int j=start,i=(j-1)/2;
                T temp
            =heap[j];
                
            while(j>0)
                
            {
                    
            if(heap[i]<temp) break;
                    
            else heap[j]=heap[i];j=i;i=(i-1)>>1;
                }

                heap[j]
            =temp;
            }

            template
            <class T>
            T MinHeap
            <T>::RemoveMin( )
            {
                T x
            =heap[0];
                heap[
            0]=heap[CurrentSize-1];
                CurrentSize
            --;
                FilterDown(
            0,CurrentSize-1);
                
            return x;
            }


            template
            <class T>
            T MinHeap
            <T>::GetMin()
            {
                
            return heap[0];
            }

            稍微改良一下啊 只需要重載<符號即可

            posted on 2009-05-08 16:57 abilitytao 閱讀(413) 評論(0)  編輯 收藏 引用

            一本久久a久久精品亚洲| 99久久精品国产高清一区二区| 99久久777色| 久久综合中文字幕| 久久这里只有精品视频99| 亚洲精品无码久久毛片| 亚洲午夜久久久久久久久久| 中文国产成人精品久久不卡| 97久久综合精品久久久综合| 免费一级欧美大片久久网| 色老头网站久久网| www.久久热.com| 国产精品一区二区久久精品涩爱 | 久久精品亚洲精品国产色婷| 韩国三级大全久久网站| 免费一级欧美大片久久网| 久久久久久久久久久久中文字幕 | 97久久精品人人澡人人爽| 蜜桃麻豆www久久国产精品| 久久久久亚洲av无码专区喷水 | 精品久久久久久国产| 91精品国产高清久久久久久91 | 精品久久久久久国产免费了| 国产精品久久久久久久app | 91久久精品国产91性色也| 亚洲国产精品无码久久98| 久久中文精品无码中文字幕| 四虎国产永久免费久久| 久久九九精品99国产精品| 伊人久久五月天| 超级碰久久免费公开视频| 中文成人久久久久影院免费观看| 激情综合色综合久久综合| 中文字幕精品无码久久久久久3D日动漫 | 久久精品国产亚洲网站| 色天使久久综合网天天| 99久久er这里只有精品18| 久久亚洲高清观看| 青青草原综合久久大伊人| 久久久久久久综合日本亚洲 | 久久亚洲精品国产精品|