自己的堆實現在C++

我必須寫在C++中我自己的實現堆，存儲類型的對象：自己的堆實現在C++

std::pair<City, int>

其中市是存儲兩個整數，代表城市COORDS和字符串的結構 - 城市名。我知道如何用普通整數來做到這一點，但使用一對值對我來說有點問題。我已經開始寫我的堆類了，但正如我所說，我不知道如何使用這些對來完成。我想堆是由該對的整數值排序的。

來源

2013-05-30 jonah_muller

試着對你的問題更具體。究竟是什麼問題？顯示您嘗試寫入的功能並解釋您遇到的問題。 – interjay

什麼意思是「排序」？堆只提供了2個操作推送和彈出最小/最大，他沒有任何排序。如果開始時所有數據都可用，那麼堆不必要，只需簡單的排序。 –

我認爲你應該實現這個類的比較運算符.. – sethi

您可以嘗試使用std::make_heap，這會將您的配對序列放入堆序中，請參閱此online example。由int值排序只，使用C++ 11 lambda表達式，將比較每一對

備選地的第二元件，因爲不能使用任何STL堆相關的算法，但給出的任何自的

template<typename RandomIt> 
void my_make_heap(RandomIt first, RandomIt last) 
{ 
    /* some algorithm using `a < b` to do comparisons */ 
}

製成實施可以重寫爲（或添加過載）

template<typename RandomIt, typename Compare> 
void my_make_heap(RandomIt first, RandomIt last, Compare, cmp) 
{ 
    /* SAME algorithm, but now using `cmp(a, b)` to do comparisons */ 
}

，然後其中lambda表達式這樣比較對稱其爲my_make_heap(first, last, int_cmp)：

typedef std::pair<City, int> Element; 
    auto int_cmp = [](Element const& lhs, Element const& rhs) { 
     return lhs.second < rhs.second; 
    };

來源

2013-05-30 12:10:43 TemplateRex

0：看到問題開始於「我必須寫自己的堆實現」，並且很可能是一項家庭作業，這個答案並不真正有用。 – Angew

我不允許使用任何STL庫。 –

@ user2342783：但你可以使用std :: pair？ – nouney

如果您知道如何做int s，您幾乎就在那裏。對待pair對象，就像您在分配時處理int一樣，但爲了進行比較，請使用.second而不是直接使用該值。

來源

2013-05-30 12:15:14 Angew

所以，從我的理解：

你的結構是這樣的，

struct node 
{ 
    int X_coord; 
    int y_coord; 
    string name; 
}

而且你需要根據「詮釋，形成了堆」對價值，把它稱爲‘X’。

所以你對是

pair<node n , int x> ;

This，是一個非常重適用於堆的適用代碼，在類中實現。

它可以很容易地修改爲您對<>值的要求。只需使用「heap.second」作爲您的關鍵值。

來源

2013-05-30 12:21:49 Spandan

自己的堆實現在C++

回答

相關問題