如何使用模板實現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

回答

相關問題