• <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>

            oyjpArt ACM/ICPC算法程序設計空間

            // I am new in programming, welcome to my blog
            I am oyjpart(alpc12, 四城)
            posts - 224, comments - 694, trackbacks - 0, articles - 6

            HEAP

            Posted on 2006-09-08 23:25 oyjpart 閱讀(777) 評論(3)  編輯 收藏 引用

            ?

            // 說實話?我還是挺喜歡HEAP這個數據結構的?寫個類的HEAP吧?呵呵
            // by?Optimistic
            // 本程序是大根堆的操作集合?以及堆排序?優先級隊列的堆實現
            #include? < string .h >
            #include?
            < iostream >
            using ? namespace ?std;

            template?
            < typename?T >
            class ?MaxHeap???????????????? // 大根堆?(本程序使用下標與結點名相同的格式)
            {
            public :
            ?MaxHeap(
            int ?MaxHeapSize? = ? 10 );
            ?
            ~ MaxHeap() {delete?[]?heap;}
            ?
            int ?Size() { return ?heapSize;}
            ?MaxHeap
            < T >& ?Insert( const ?T & ?x);
            ?MaxHeap
            < T >& ?Delete(T & ?x);
            ?
            void ?MakeHeap(T? * ?a,? int ?size,? int ?ArraySize);
            ?T?Max()
            ?
            {
            ??
            if (heapsize? > ? 0 )????? // 判溢出
            ?? return ?heap[ 1 ];
            ?}

            private :
            ?T
            * ?heap;
            ?
            int ?heapSize;
            ?
            int ?MaxSize;?
            }
            ;

            template?
            < typename?T >
            MaxHeap
            < T > ::MaxHeap( int ?MaxHeapSize)?????????
            {
            ?MaxSize?
            = ?MaxHeapSize;
            ?heap?
            = ? new ?T[MaxSize + 1 ];
            ?heapSize?
            = ? 0 ;
            }


            template?
            < typename?T >
            MaxHeap
            < T >& ?MaxHeap < T > ::Insert( const ?T & ?x)? // 堆的插入?由葉結點向上找位置?在sort中是不需要插入的
            {
            ?
            if (heapSize? < ?MaxSize)????
            ?
            {
            ??heapSize
            ++ ;
            ??
            int ?i? = ?heapSize,?ic? = ?i / 2 ;
            ??
            while (ic? >= ? 1 )
            ??
            {
            ???
            if (x? <= ?heap[ic])? break ;
            ???heap[i]?
            = ?heap[ic];
            ???i?
            = ?ic;
            ???ic?
            = ?i? / ? 2 ;
            ??}

            ??heap[i]?
            = ?x;
            ?}

            ?
            return ? * this ;
            }


            template?
            < typename?T >
            MaxHeap
            < T >& ?MaxHeap < T > ::Delete(T & ?x)??????? // 堆的刪除?即根結點的刪除?從上到下
            {
            ?
            // 在操作上相當與對最后一個結點從上到下的插入
            ? if (heapSize? > ? 0 )
            ?
            {
            ??x?
            = ?heap[ 1 ];
            ??T?y?
            = ?heap[heapSize -- ];
            ??
            int ?i? = ? 1 ,?ic? = ? 2 ;?????????????? // i記錄當前查詢結點?ic記錄其子結點
            ?? while (ic? <= ?heapSize)???????????????
            ??
            {
            ???
            if (ic + 1 ? <= ?heapSize? && ?heap[ic]? < ?heap[ic + 1 ])?ic ++ ;
            ???
            if (y? >= ?heap[ic])? break ;
            ???heap[i]?
            = ?heap[ic];
            ???i?
            = ?ic;
            ???ic?
            = ? 2 * i;
            ??}

            ??heap[i]?
            = ?y;
            ?}

            ?
            return ? * this ;
            }


            template?
            < typename?T >
            void ?MaxHeap < T > ::MakeHeap(T? * ?a,? int ?size,? int ?ArraySize)? // 建堆:把數組堆化并處理成大根堆
            {
            ?
            // 堆化
            ?delete?[]?heap;
            ?heap?
            = ? new ?T[size + 1 ];
            ?memcpy(heap,?a,?(size
            + 1 ) * sizeof (T));?????? // 此處不要忘記乘sizeof(T)
            ?heapSize? = ?size;
            ?MaxSize?
            = ?ArraySize;
            ?
            // 處理堆
            ? int ?i? = ?heapSize / 2 ;
            ?
            for (;?i? >= ? 1 ;?i -- )???????????????????? // 從小到上依次調整
            ? {
            ??T?y?
            = ?heap[i];
            ??
            int ?ic? = ? 2 * i;
            ??
            while (ic? <= ?heapSize)?
            ??
            {
            ???
            if (ic + 1 ? <= ?heapSize? && ?heap[ic + 1 ]? > ?heap[ic])?ic ++ ;
            ???
            if (y? >= ?heap[ic])? break ;
            ???heap[ic
            / 2 ]? = ?heap[ic];
            ???ic?
            = ? 2 * ic;
            ??}

            ??heap[ic
            / 2 ]? = ?y;
            ?}

            }


            template?
            < typename?T >
            void ?HeapSort(T? * ?a,? int ?n)
            {
            ?MaxHeap
            < T > ?H( 0 );
            ?H.MakeHeap(a,?n,?n);
            ?T?x;
            ?
            for ( int ?i? = ?n;?i? >= ? 1 ;?i -- )
            ?
            {
            ??H.Delete(x);
            ??a[i]?
            = ?x;
            ?}

            }


            int ?main()
            {
            // ?freopen("heap.in",?"r",?stdin);
            ? int ?size,?i,? * ?a;
            ?printf(
            " Please?input?the?size?of?array:\n " );
            ?scanf(
            " %d " ,? & size);
            ?a?
            = ? new ? int [size + 1 ];
            ?printf(
            " Please?input?the?array?to?be?sorted:\n " );
            ?
            for (i = 1 ;?i <= size;?i ++ )
            ??scanf(
            " %d " ,? & a[i]);
            ?HeapSort(a,?size);
            ?
            for (i = 1 ;?i <= size;?i ++ )
            ??printf(
            " %4d " ,?a[i]);
            ?printf(
            " \n " );
            ?system(
            " Pause " );

            ?
            return ? 0 ;
            }


            Feedback

            # re: HEAP  回復  更多評論   

            2006-09-15 17:26 by
            heap, 好想學, 不知道我為什么沒講heap的書...-_-

            # re: HEAP  回復  更多評論   

            2006-09-15 23:53 by Optimistic
            第一次遇到HEAP的時候好喜歡啊 呵呵 真是一個好東東!

            # re: HEAP  回復  更多評論   

            2006-10-25 22:40 by Asp
            不知道以后數據結構會不會講……
            亚洲AV伊人久久青青草原| 欧美日韩精品久久久久| 国产精品美女久久久久久2018| 久久久www免费人成精品| 亚洲精品乱码久久久久久中文字幕 | 伊人久久精品影院| 久久国产精品无码一区二区三区| 国产农村妇女毛片精品久久| 国内精品久久久久影院亚洲| 精品午夜久久福利大片| 日韩中文久久| 亚洲一区二区三区日本久久九| 伊人久久大香线蕉成人| 精品久久久久一区二区三区| 久久精品午夜一区二区福利 | 国产精品久久久久AV福利动漫| 久久久WWW成人免费毛片| 久久久久久夜精品精品免费啦| 香港aa三级久久三级老师2021国产三级精品三级在 | 国产成人无码精品久久久性色| 国产精品美女久久久免费| 久久久久久九九99精品| 国产美女亚洲精品久久久综合| 久久久综合香蕉尹人综合网| 国产精品久久久久久久久鸭| 久久婷婷激情综合色综合俺也去| 亚洲欧美久久久久9999 | 情人伊人久久综合亚洲| 久久久久久久久久久久中文字幕| 久久人与动人物a级毛片| 亚洲国产精品综合久久网络| 国内精品久久久久久不卡影院 | 欧美日韩中文字幕久久久不卡| 国产成人精品综合久久久| 国产精品永久久久久久久久久| 久久99国产精一区二区三区| 国产午夜久久影院| 国产激情久久久久影院| 久久精品国产精品亚洲人人| 久久国产影院| 久久www免费人成看片|