C++數據結構堆

我一直在試圖在我的程序中實現一個堆。在我看來，堆和二叉樹是一樣的。這種情況下，所有堆，如最小堆和最大堆，因爲所有正在做的事情是遍歷樹穿越最大/最小節點到頂部？C++數據結構堆

此外，我讀過使用一維數組只有當我們有一個完整的二叉樹。如果我們沒有一個完整的二叉樹，使用另一個朋友類的類會更有益處？這是爲什麼？如：

template<class T> class BT; // forward declartion -> added at edit 

template<class T> 
class BTNode{ 
    friend class BT<T>; // not sure why we need two classes 
private: 
    T data; 
    BTNode<T> *leftChild; // what is the benefit of making a object Node? 
    BTNode<T> *rightChild; 
}; 

template<class T> 
class BT{ 
private: 
    BTNode<T> *root; // what is the benefit of having this root in another class? 
};

提前致謝。

來源

2012-11-17 Chris

這就是在諸如'std :: priority_queue'等容器中使用的東西，並且被稱爲**堆**。 – Aesthete

@Aesthete：挑選，我知道。 heap是一個具體的數據結構; 「優先級隊列」是可以用堆實現的抽象數據類型（即，接口），但也可以以其他方式實現。 'std :: priority_queue'是一個容器適配器，而不是一個容器。 – rici

這是默認實現，語義挑剔完全減損了我試圖創建的點，這是針對之前已被刪除的註釋。 – Aesthete

標準庫中有一個非常好的堆實現;你應該看看它（但它也是一個有用的學習練習，也可以編寫自己的練習）。

二進制堆是一個二叉樹，但它作爲一個向量有效存儲。鏈接是隱含的。也就是說，位於i（零基）的節點的孩子在2i+1和2i+2。（堆中最多隻有一個節點只有一個子節點）。這意味着你實際上並不需要存儲鏈接，所以在小數據對象（如整數）的情況下，至少節省了三分之二所需的空間。

Wikipedia在二元堆（通常存儲在向量中的類型）上有一篇很好的文章，但它也有其他類型的heaps上的一些文章。

來源

2012-11-17 03:19:02 rici

是的，'std :: make_heap（beg，end）;'其中beg和end是'std :: vector :: iterator'類型。 – Aesthete

我會看看STL庫。這似乎是一個很好的開始，因爲我必須實現一個沒有STL庫的最小堆。 – Chris

C++數據結構堆

回答

相關問題