积木

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 阅读(310) 评论(0)  编辑 收藏 引用 所属分类: VC / C++

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理