《STL源码剖析》读书笔记之序列式容器(3)

1.heap

heap不属于STL容器组件,它是priority queue的底层实现机制。

(1)push_heap算法

向堆中加入元素,首先将要加入的元素放到堆所在数组的末端,,然后再对这个元素进行上溯操作,直到新堆合法为止。如下图所示:

(2)pop_heap算法

pop_heap操作取走堆中的最大(小)值。根据堆的特性,堆的最大(小)值必定是堆所存数组的第一个元素。取堆的最大(小)元素时,将堆的最后一个元素和堆的第一个元素互换,然后再对第一个元素进行下溯操作,直到新堆满足堆的定义。下图给出的是一个例子:

(3)sort_heap算法

每次pop_heap操作都能取得heap的最大(小)值,则持续的对heap进行pop_heap操作,直到heap为空时,便得到了heap的有序序列。其过程如下所示:

2.priority_queue

顾名思义,priority_queue表示优先队列。STL里面的priority_queue默认由heap来完成,后者是一个vector存储complete binary tree。

priority_queue的完整定义如下:

幸福就是重复。每天跟自己喜欢的人一起,通电话,

《STL源码剖析》读书笔记之序列式容器(3)

相关文章:

你感兴趣的文章:

标签云: