• <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 閱讀(320) 評論(0)  編輯 收藏 引用 所屬分類: VC / C++
            精品久久久无码中文字幕| 精品永久久福利一区二区 | 久久一区二区三区99| 久久久久成人精品无码| 国产精品成人久久久| 少妇高潮惨叫久久久久久 | 欧美日韩精品久久久免费观看| 理论片午午伦夜理片久久 | 亚洲精品乱码久久久久久蜜桃图片 | 四虎亚洲国产成人久久精品| 亚洲日韩中文无码久久| AAA级久久久精品无码区| 久久精品国产色蜜蜜麻豆| 久久99免费视频| 久久久久国产精品人妻| 久久久久国产一区二区| 97r久久精品国产99国产精| 区亚洲欧美一级久久精品亚洲精品成人网久久久久 | 久久久久一级精品亚洲国产成人综合AV区| 伊人久久精品影院| 国产精品综合久久第一页| 亚洲αv久久久噜噜噜噜噜| 久久综合五月丁香久久激情| 久久久久四虎国产精品| 色综合久久无码中文字幕| 久久综合九色欧美综合狠狠| 国产一区二区精品久久凹凸| 狠狠干狠狠久久| 久久久精品2019免费观看| 亚洲愉拍99热成人精品热久久| 色偷偷91久久综合噜噜噜噜| 久久99精品久久久久久噜噜| 久久久中文字幕| 久久免费小视频| 秋霞久久国产精品电影院| 精品久久一区二区| 情人伊人久久综合亚洲| 国产精品免费久久久久影院 | 一级做a爱片久久毛片| 久久99热精品| 久久国产成人|