最小堆和最大堆之間切換基於標記

我已經定義了一個minheap如下最小堆和最大堆之間切換基於標記

typedef priority_queue<megePartitions_t,vector<megePartitions_t>,compareMergePartition> mergePartitionFilesQ_t;

該比較器被定義如下

struct compareMergePartition 
{ 
    bool operator()(const megePartitions_t &lhs,const megePartitions_t &rhs) 
    { 
     return *(lhs._pair) > *(rhs._pair); 
    } 
};

我使用的定義minheap如下

mergePartitionFilesQ_t mergeQ

現在，我想根據標誌在minheap和maxheap之間切換，我應該改變比較器的構造使用者可以拿起旗幟並用它在比較之間或之間翻轉，或者有更好的方法。感謝您的幫助。

答：我覺得沒有必要使用函子，所以我切換到函數指針，並根據標誌選擇適當的函數。

if(m_builtAcending) 
    comparator = compareMergePartitionAsc; 
else 
    comparator = compareMergePartitionDes; 
mergePartitionFilesQ_t mergeQ(comparator);

謝謝freitass的幫助

來源

2013-05-06 vgeta

@john你的意思是，兩個不同的函數，如何typedef優先級隊列？ – vgeta 2013-05-06 14:27:22

你能再詳細一點嗎？你想採取一個現有的堆，切換標誌，然後重新運行'make_heap'從最小值改變到最大值或相反？ – 2013-05-06 14:29:49

@MarkB不，我不想重建基於標誌的現有堆，這是我想要聲明堆對象時，「mergePartitionFilesQ_t mergeQ」mergeQ可以是基於標誌的minHeap或maxHeap。 – vgeta 2013-05-06 14:34:16

您可以定義接受一個比較函數和實例它傳遞std::less或std::greater構造你的仿函數，如下所示：

template<class Comp> 
struct compareMergePartition 
{ 
    Comp comp; 
    compareMergePartition(Comp comp) : comp(comp) {} 
    bool operator()(const megePartitions_t &lhs,const megePartitions_t &rhs) 
    { 
     return comp(*(lhs._pair), *(rhs._pair)); 
    } 
}; 

// Min heap 
typedef priority_queue<megePartitions_t,vector<megePartitions_t>,compareMergePartition(std::less<megePartitions_t>())> mergePartitionFilesQ_t; 

// Max heap 
typedef priority_queue<megePartitions_t,vector<megePartitions_t>,compareMergePartition(std::greater<megePartitions_t>())> mergePartitionFilesQ_t;

編輯：這個答案是假設你在施工時知道你想要的。它不適用於即時更改。

來源

2013-05-06 14:35:01 freitass

+1這將是我的答案。 – 2013-05-06 14:59:24

@freitass你已經爲模擬函子，但不使用它 – vgeta 2013-05-06 15:14:21

@Gopikanna沒有必要顯式指定類型，因爲它可以由構造函數的參數推斷。 – freitass 2013-05-06 15:50:50

一種方法是添加一個構造函數，因爲當您更改標誌時，您的數據順序將不正確;你將不得不重建整個優先隊列。所以也許你可以有兩個隊列，一個是最小堆，一個是最大堆？當標誌的值改變時，將數據複製到另一個？（由freitass提供的實現是一個很好的恕我直言）

來源

2013-05-06 14:38:36 Kourosh

最小堆和最大堆之間切換基於標記

回答

相關問題