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。