如何使用模板实现minheap

我需要创建一个包含节点的minheap模板。如何使用模板实现minheap

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

2010-09-19 Nadav Stern

-1请使用标点符号和大小写。 – 2010-09-19 09:55:58

@Space。你有足够的代表来编辑问题并修复那样的错误。它比downvoting更好一点。 – PaulG 2010-09-19 10:44:01

@PaulG：在用户搞砸他们的代码格式的情况下，因为他们不知道这些东西如何工作（或类似的东西），我同意。但使用标点符号和大写字母不是别人应该为您解决的问题。如果有人以这种方式提出问题，那只意味着他们懒得以可读的方式输入。 – 2010-09-19 10:50:38

通常情况下，从不使用显式节点来实现分层堆栈 - 因为堆总是被填满（“完成”），因此具有定义良好的结构，这将会是不必要的低效率，因为处理节点和节点链接引入了相当多的开销，更不用说破坏引用的局部性，导致缓存未命中和性能较差。

（这同样适用于过程的最大堆。）

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

来源

2010-09-19 09:47:24

事情是我做的需要节点...我需要在堆中的节点提取他在log（n）运行时，我需要建立一个数据结构，其中包含一个地图和一个小堆，这两个结构应该能够互相沟通，所以我将能够在log（n）运行时提取/更新/删除运行时间，我考虑过在这两个结构中都有节点，并让它们与heother中的节点进行通信。 – 2010-09-19 09:58:22

不，因为两个容器都会尝试管理节点的内存。使用std :: heap实现，指向其他数据和适当的比较函数。无论如何你都会得到O（lnN），而没有指向堆内节点的指针。 – 2010-09-19 10:04:22

@Navad：不，这不是一堆堆。堆是一个定义明确的数据结构，其高效操作具有明确的算法。你所描述的不是一堆 - 它是一个模仿堆的不同数据结构。查看您的可信算法教科书或NIST目录中的算法和数据结构或您的讲义，以查看堆应该如何工作。 – 2010-09-19 10:19:40

基本上节点不需要用节点作为模板类来实现。的实现可能是这样的声明：

template <class T> 
class MinHeap { 
private: 
    std::vector<T> _heap; 
    int _maxSize; 
    int _size; 

public: 
    MinHeap(int maxSize); 
    ~MinHeap(); 
    void Insert(T elem); 
    T RemoveMin(); 

private: 
    int LeftChild(int pos); 
    int RightChild(int pos); 
    int Parent(int pos); 
    boolean IsLeaf(int pos); 
    void Swap(int pos1, int pos2); 
    void PushDown(int position); 
};

来源

2010-09-19 10:00:08 rkellerm

感谢您的回答，但我不明白，节点应该在哪里？我应该实现一个应该是模板1的节点类，并且minheap会将此节点作为输入（类T）？ – 2010-09-19 10:14:01

@Nadav，这意味着节点的类型取决于您在T处的决定.T可以是整数，字符或实现比较运算符的任何类。例如：MinHeap intMeanHeap; – rkellerm 2010-09-19 11:27:01

如何使用模板实现minheap

回答

相关问题