[c++] Sortowanie Przez Kopcowanie.

[danrok]

Witam,

mam taki problem. Zaimplementowałem algorytm PRIME, do wyszukiwania MST w grafie. Polega on na tym, iż na początku jesteśmy w losowym wierzchołku i mamy dostępne jego incydentne. Następnie następuje wyszukiwanie minimalnej wagi z wierzchołkiem incydentnym i dodanie go. Cykl powtarza się aż do uzyskania drzewa spójnego. W algorytmie kluczowe jest szybkie wyszukiwanie minimalnej wagi i z tym jest problem.

 

Załóżmy, że posiadamy 300 wierzchołków, co daje nam macierz (300x300). Przy pierwszym sortowaniu mamy wiec 300 wag do posortowania, co odbywa się szybko. Po dodaniu wierzchołka posiadamy już jednak 600 incydentnych, czyli 600 wag do sortowania, później 900, 1200 aż do 300*300. Sortowanie introspektywne z C++ nie daje rady i wpadłem na pomysł sortowania przez kopcowanie. Jego efektywność byłaby zapewne dużo lepsza w tym wypadku. Mam jednak problem z implementacją z STL-a.

 

Wiem, że kopiec tworzy się za pomocą make_heap(v.begin(),v.end(),compare_function). Później jednak zależy mi na dorzucaniu elementów za pomocą funkcji push_heap(...). Kopiec STL jednak na szczycie posiada wartość maksymalną. Da się jakoś go odwrócić, by uzyskać tam wartość minimalną?

[Jastrząb]

Jako 3 parametr w make_heap() użyj std::greater<typ_sortowany>()

[danrok]

Dzięki, problem rozwiązany:)