與節點指針STL堆

Question

我有我想要通過使用STL功能

make_heap(Iterator , Iterator, comp) 
pop_heap(Iterator, Iterator, comp) 

適用於節點指針的向量，以創建一個堆成員

int weight; 
Node *left; 
Node *right; 

節點類。我如何爲這些函數創建比較對象（或比較函數）？

Answer 1

如果您通過operator<爲您的對象提供嚴格的弱排序，則可以調用make_heap,pop_heap等的超載，它們甚至不需要第三個參數。 comp是如此您可以提供自定義比較，如果您選擇。

class Node 
{ 
int weight; 
Node *left; 
Node *right; 

public: 
bool operator<(const Node& rhs) const { return weight < rhs.weight; } 
}; 

Answer 2

struct node_comparison : public std::binary_function< const Node*, const Node*, bool > 
{ 
    bool operator()(const Node* const a, const Node* const b) const 
    { 
     return a->weight < b->weight; 
    } 
}; 

注意，這comparsion對象比較僅的權重，但我認爲這是期望的行爲。