如何使用模板实现minheap [英] how to implement minheap using template

问题描述

我需要创建一个包含节点的minheap模板。

I need to create a minheap template which includes nodes in it.

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

The problem I have is that I don't know if I need to create a node template class as well, or should it be included inside the heap template class as a struct?

推荐答案

最小堆不是通常使用显式节点实现的（完成），因此具有良好定义的结构，这将是不必要的低效的，因为节点和节点链路的处理引入相当多的开销，更不用说破坏参考的局部性，导致高速缓存缺失和差的性能。

Min heaps aren’t usually (never?) implemented using explicit nodes – since a heap is always left-filled ("complete") and thus has a well-defined structure, that would be unnecessarily inefficient since the handling of nodes and node links introduces quite a bit of overhead, not to mention destroying locality of reference, leading to cache misses and poor performance.

（当然也适用于最大堆）

(The same goes for max heaps of course.)

而是使用数组来实现。事实上，C ++标准库已经包括了 make_heap ， push_heap 和 pop_heap 用于迭代器范围。将它们与向量结合使用，你就得到了你的堆。

Instead, they are implemented using arrays. In fact, the C++ standard library already includes the functions make_heap, push_heap and pop_heap to work on iterator Ranges. Use them in conjunction with a vector and you got your heap.

这篇关于如何使用模板实现minheap的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！