c++ - 如何使用模板实现minheap

Question

我需要创建一个包含节点的最小堆模板。

我的问题是我不知道我是否也需要创建一个节点模板类，或者它是否应该作为一个结构包含在堆模板类中？

Answer 1

最小堆通常(从不？)使用显式节点实现——因为堆总是左填充(“完整”)，因此具有定义明确的结构，这将是不必要的低效率，因为节点的处理和节点链接引入了相当多的开销，更不用说破坏引用的局部性，导致缓存未命中和性能不佳。

(当然最大堆也是一样。)

相反，它们是使用数组实现的。事实上，C++ 标准库已经包含函数 make_heap、push_heap 和 pop_heap 来处理迭代器范围。将它们与 vector 结合使用，您就得到了堆。