rambo

STl中的堆

STL中的优先队列

首先这是一个队列,只允许在底端加入元素,并从顶端取出元素,除此之外别无其他存取元素的途径。

priority_queue带有权值观念,元素并非按照被推入的次序排列,而是自动按照元素的权值排列。权值最高者,排在最前面。缺省情况下priority_queue利用一个MAX-HEAPIFY完成,以vector表现的完全二叉树(complete binary tree)。

QQ截图20150907001934

queue以底部容器vector完成其所有工作,具有这种“修改某物接口,形成另一种风貌”之性质这,称为配接器(adapter)。STL priority_queue被归类为container adapter。

priority_queue没有迭代器

priority_queue不提供遍历功能,也不提供迭代器。

Container 必须是用数组实现的容器,比如 vector,deque 但不能用 list。STL里面默认用的是 vector. 比较方式默认用 operator< , 所以如果把后面俩个
参数缺省的话,优先队列就是大顶堆,队头元素最大

QQ截图20150907003605

QQ截图20150907004936

VS中的heap

QQ截图20150801203436

QQ截图20150906171239

 

 

参考资料:

1)http://blog.csdn.net/rushkid02/article/details/7687125

2)侯捷   《STL源码剖析》