堆操作算法：提升C＋＋STL的性能

在计算机算法领域，“堆”（Heap）通常是指一种组织序列元素的方式。“堆”的第一个元素通常是具有最大值的元素。STL的算法库中提供了部分堆操作算法：push_heap（）、pop_heap（）、sort_heap（）、make_heap（）等。

就其应用于排序而言，“堆”是一种特别的元素组织方式，即以序列式群集形式存在的二叉树。“堆”具有两大性质：堆中的第一个元素的值总是最大；能够在对数时间内增加或移除一个元素。

堆的默认排序规则为“operator＜”。程序开发人员还可以使用自定义的排序准则。下面分别讲述各种“堆”相关的算法。

1.make_heap（）算法

make_heap（）算法的原型为：

上述两种形式均可实现将［_First，_last］中的元素转化为“堆”。参数_Comp是二元判断式，是排序准则。使用“堆”处理的条件是：元素多于1个。如果仅有1个元素，没必要使用“堆”。也可以认为单个元素本身就是“堆”。

2.push_heap（）算法

push_heap（）算法可实现在其参数（指定区间）中插入一个元素，新插入的元素放在堆栈末尾，即尾指针处。使用push_heap（）算法时，必须保证区间原有的元素已是既定的“堆”。其原型为：

3.pop_heap（）算法

pop_heap（）算法的作用是删除在迭代器［_First，_Last］指定范围（“堆”）内的元素序列中的最大元素（第一个元素）。剩余的其余元素成为一个新的“堆”。其原型为：

(www.xing528.com)

4.sort_heap（）算法

sort_heap（）算法的作用是对其参数迭代器指定的范围内元素进行排序。其原型为：

sort_heap（）算法可以使堆［beg，end］转化为一个已序的序列。算法执行之后，该区间及其区间内的元素，就不再是“堆”了。

提示

堆的内部数据结构为二叉树。输出的堆数据有时看上去有些乱。其实并不乱，堆数据在内存中是以二叉树的形式存在的。

例4-29

例4-29的执行效果如图4-29所示。

图4-29 例4-29的执行效果