8 实现优先队列（上）

本项目GitHub： HuangCheng72/HCSTL: 我的STL实现 (github.com): https://github.com/HuangCheng72/HCSTL

进入正文。

在上一篇中，我们已经给 vector 和 list 完成了迭代器的部分，现在我们的这两个容器可以通过迭代器操作容器里面的数据了，现在我们可以实际地应用这两个容器了，我们以 vector 为例。

优先队列（Priority Queue）是一种常用的数据结构，每次取出的元素都是队列的全部元素中具有最高优先级的元素（具体视排序规则而定），优先队列一般是基于堆（heap）结构实现的，通常是通过数组或者二叉树表示。我们知道，vector本质上是一个可变数组，因此我们可以考虑在 vector 的基础上实现优先队列。

像这样，在某种组件的基础上，实现或者衍生出另一种组件的过程，就叫适配（配接，Adaption），所得到的新组件，就是所谓的适配器（配接器，Adaptor）。适配器相比较于原组件，是一种特定方向的发展，着重加强了某方面的能力。适配器的优点在于它以原组件为底层数据结构，贯彻了代码复用的原则，大大减少了重复的工作量，缺点在于它依赖于原组件，如果提供的原组件性能不佳，则适配器的性能必然不佳。

新建头文件 queue.h，暂时只考虑C++内建类型数据 ，按照以下原型实现一个优先队列：

学习数据结构与算法的时候，通常我们建立堆的过程是：

在数组中，下标 i 从1起算时， i 的孩子结点是 i * 2和 i * 2 + 1 。

类似的，如果 i 从0起算，那么根据数学推理有，( i + 1 ) 的孩子结点是 ( i + 1 ) * 2 和 ( i + 1 ) * 2 + 1。

所以 i 的孩子结点是， i * 2 + 1 和 i * 2 + 2。

最好采用 i 从 0 起算的做法，因为我们使用的是vector，返回top的时候可以返回的是vector.front()。

而且最重要的是我们不知道输入的数据是什么，没办法在 i = 0 处放置哨兵结点。

当然，如果要实现下标 i 从1起算也是可以的，本教程对此不讨论，请自行实现。

我的实现如下：

在 main.cpp 中简单测试一下：

输出正确结果，我们可以换一种内置类型比如double来试试。

一切正常。

欢迎访问本项目的GitHub仓库，如果对您有帮助，麻烦给项目一个star，谢谢！

HuangCheng72/HCSTL: 我的STL实现 (github.com): https://github.com/HuangCheng72/HCSTL