我需要创建一个包含节点的最小堆模板。
我的问题是我不知道我是否也需要创建一个节点模板类，或者它是否应该作为一个结构包含在堆模板类中？
最佳答案
最小堆通常(从不？)使用显式节点实现——因为堆总是左填充(“完整”)，因此具有定义明确的结构，这将是不必要的低效率，因为节点的处理和节点链接引入了相当多的开销，更不用说破坏引用的局部性，导致缓存未命中和性能不佳。
(当然最大堆也是一样。)
相反，它们是使用数组实现的。事实上，C++ 标准库已经包含函数 make_heap、push_heap 和 pop_heap 来处理迭代器范围。将它们与 vector 结合使用，您就得到了堆。
关于c++ - 如何使用模板实现minheap，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3745194/