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