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

            積木

            No sub title

              C++博客 :: 首頁 :: 聯系 :: 聚合  :: 管理
              140 Posts :: 1 Stories :: 11 Comments :: 0 Trackbacks

            常用鏈接

            留言簿(1)

            我參與的團隊

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            1) 正如書中所述,stl所述的heap都是max-heap。即:父節點的“值”[注釋1],永遠是 >= 其子節點的值。
            2) 正如書中所述,stl所述的heap不歸屬于容器。因為它是一組算法。這些算法的實現原理,在此[注釋2],是以一棵完全二叉樹來設計的。
            3) 以下對各個max-heap接口算法的小結:

            a) make_heap()
            說明:顧名思義,該接口就是用來“創建”一個heap的。是對原有的一堆任意存放的數據,按照第一點所述的規則,進行“排列”(注意:不是排序)。
            示例(來自書中例子,抄出來,經常看,印象會更深刻。在此,我們重在理解算法與掌握運用):
            int ai[9] = {0, 1, 2, 3, 4, 8, 9, 3, 5};
            vector<int> ivec(ia, ia + 9);
            make_heap(ivec.begin(), ivec.end());//調用后,ivec中的數據的排列將改變掉,并且已經是按max-heap的結構存儲的。
            for (int i = 0; i < ivec.size(); i++)
                cout << ivec[i] << ' ';  // 9 5 8 3 4 0 2 3 1
            cout << endl;

            b) push_heap()
            說明:將新push_back()到ivec的末尾元素按照max-heap的要求規則,進行位置調整。使得新的整個ivec中的元素排列規則符合max-heap的規則要求。
            注意:
                1) push_heap()的操作,一定都是針對最末尾的那個元素,對它的位置按照max-heap的要求,進行重新調整的。
                2) 執行push_heap()操作前,一定一定要保證除了最末尾的那個元素外,前面的元素的排列規則一定都滿足max-heap()的規則存放的。
            示例:
            ivec.push_back(7);
            push_heap(ivec.begin(), ivec.end());
            for (int i = 0; i < ivec.size(); i++)
                cout << ivec[i] << ' '; // 9 7 8 3 5 0 2 3 1 4
            cout << endl;

            c) pop_heap()
            說明:該接口意即:要從整個heap中,取出元素。但這里取出的一定是“值”最大的那個元素。而不是像vector或list等那樣,可以取出任意位置的元素。
            注意:
                1) 調用該接口“取出”元素后,其實該元素(即:“值”最大的那個元素)并未真正被取出來,而是將該元素放到了ivec的最末尾位置。(也正是因此,如果對整個ivec進行多次的pop_heap()操作,即可完成ivec的排序功能)
                2) 正如 注意1) 所述的,則在pop_heap()后,ivec除了最末尾的那個元素外,前面的元素仍然是保持著max-heap的規則存儲的。
            示例:
            pop_heap(ivec.begin(), ivec.end());
            cout << ivec.back() << endl; // 9. return but not remove.
            ivec.pop_back(); // remove last elem and no return;

            d) sort_heap()
            說明:顧名思義,是對一個heap進行排序。
            注意:
                  1) 排序后的“heap"(即:原始的heap)將不復存在(理由很簡單:排序后,原heap中的元素的存儲規則不符合max-heap的規則,因此排序后的,就不能再稱為heap)
            示例:
            sort_heap(ivec.begin(), ivec.end());
            for (int i = 0; i < ivec.size(); i++)
                cout << ivec[i] << ' '; // 0 1 2 3 3 4 5 7 8
            cout << endl;

            補充:max-heap的隱式表達式的push_heap()與pop_heap()操作時間都只有:O(logN)。一種算是比較居中的,還算不錯的時間性能參考值。

            最后再說兩點:
               1) 只要深刻理解了以上算法與接口的使用,對實際項目的動作,個人認為,是很有價值的。另外,理解了heap的原理,則我們也十分容易priority queue的實現細節。
               2) 對知識的掌握,還是重在理解。

            以上表述有誤之處,還望大伙多多指正啊。。:)

            [注釋1]:此處的值:我們可以當它是節點本身的值,也可以當它是某種權值。依自己使用需要而定。
            [注釋2]:指的是隱匿表達式實現的heap.即:以完全二叉樹方式實現的heap。
            posted on 2012-11-21 12:07 Jacc.Kim 閱讀(327) 評論(0)  編輯 收藏 引用 所屬分類: VC / C++
            婷婷综合久久中文字幕蜜桃三电影| 久久AAAA片一区二区| 狠狠色伊人久久精品综合网| 亚洲国产精品无码久久久秋霞2| 国内精品综合久久久40p| 亚洲国产另类久久久精品| 曰曰摸天天摸人人看久久久| 日韩十八禁一区二区久久| 亚洲精品美女久久久久99| 97久久精品无码一区二区天美| 国内精品久久久久影院网站 | 久久天天婷婷五月俺也去| 亚洲午夜久久久影院| 久久国产视频99电影| 伊人久久精品无码二区麻豆| 精品久久综合1区2区3区激情| 人妻丰满AV无码久久不卡| 久久久久久久久久久免费精品| 无码国产69精品久久久久网站| 日本久久久久久久久久| 久久免费精品视频| 久久99精品久久久大学生| 久久久精品人妻无码专区不卡| 国产精品久久久久久福利漫画| 久久久久亚洲AV无码观看| 久久福利片| 青青草国产成人久久91网| 久久无码人妻一区二区三区午夜| 91精品国产91热久久久久福利| 久久91精品综合国产首页| 久久人人爽人人爽人人av东京热 | 久久精品国产亚洲麻豆| 91久久九九无码成人网站| 久久99精品久久久久久秒播| 日韩美女18网站久久精品| 人妻无码αv中文字幕久久 | 久久婷婷五月综合色高清| 久久香蕉国产线看观看乱码| 人人狠狠综合88综合久久| 久久精品中文闷骚内射| 久久久久人妻一区精品果冻|