C++ min heap avec le type défini par l'utilisateur

J'essaye d'implémenter un heap min en C++ pour un type struct que j'ai créé. J'ai créé un vecteur du type, mais il s'est écrasé quand j'ai utilisé make_heap dessus, ce qui est compréhensible car il ne sait pas comment comparer les éléments du tas. Comment créer un min-heap (c'est-à-dire, l'élément supérieur est toujours le plus petit dans le tas) pour un type struct?C++ min heap avec le type défini par l'utilisateur

Le struct est ci-dessous:

struct DOC{ 

int docid; 
double rank; 

};

Je veux comparer les structures DOC utilisant l'élément de rang. Comment ferais-je cela? J'ai essayé d'utiliser une file d'attente prioritaire avec une classe de comparaison, mais cela a également planté, et il semble également stupide d'utiliser une structure de données qui utilise un tas comme base sous-jacente quand ce dont j'ai réellement besoin est un tas.

Merci beaucoup, bsg

Source

2010-04-04 bsg

Quelle est votre définition de «it crashed»? Sûrement, si vous n'avez pas de foncteur ou d'opérateur de comparaison, vous obtiendrez des erreurs de compilation. – sellibitze

Non, je ne l'ai pas fait. Certainement pas avec la file d'attente prioritaire, qui a un opérateur surchargé défini, et je ne pense pas non plus avec make_heap. Bien qu'il se pourrait que dans le dernier cas, j'ai eu une erreur de compilation. La première fois, cependant, il compilé bien mais s'est écrasé à l'exécution. – bsg

Si vous essayez d'utiliser make_heap avec deux arguments seulement, vous devez avoir un opérateur sellibitze

Ajouter un opérateur de comparaison:

struct DOC{ 

    int docid; 
    double rank; 
    bool operator<(const DOC & d) const { 
     return rank < d.rank; 
    } 
};

Les structures peuvent avoir presque toujours utilement un constructeur, donc j'ajouter:

DOC(int i, double r) : docid(i), rank(r) {]

à la structure aussi bien.

Source

2010-04-04 09:46:20

Autant que je peux dire cela conduirait à un "tas maximum". Mais il veut un "min tas" qui nécessite un foncteur qui renvoie vrai si et seulement si le premier argument est plus grand que le second. – sellibitze

Merci beaucoup! J'ai fini par utiliser une file d'attente prioritaire, car elle avait plus de fonctions dont j'avais besoin, mais j'ai créé un constructeur et surchargé les opérateurs < and > comme vous l'avez montré et ça a marché! – bsg

@bsg, si "ça a marché" de cette façon, vous avez posé la mauvaise question et un "max heap" est ce que vous vouliez. Décide toi. – sellibitze

Créez simplement votre propre "foncteur" pour la comparaison. Puisque vous voulez un « tas min » votre fonction de comparaison doit se comporter comme le plus grand que l'opérateur:

#include <iostream> 
#include <vector> 
#include <algorithm> 

struct doc { 
    double rank; 
    explicit doc(double r) : rank(r) {} 
}; 

struct doc_rank_greater_than { 
    bool operator()(doc const& a, doc const& b) const { 
     return a.rank > b.rank; 
    } 
}; 

int main() { 
    std::vector<doc> docvec; 
    docvec.push_back(doc(4)); 
    docvec.push_back(doc(3)); 
    docvec.push_back(doc(2)); 
    docvec.push_back(doc(1)); 
    std::make_heap(docvec.begin(),docvec.end(),doc_rank_greater_than()); 
    std::cout << docvec.front().rank << '\n'; 
}

Il est important que vous utilisez toujours la même fonction de comparaison dans d'autres opérations de tas.

Source

2010-04-04 10:08:28 sellibitze

C++ min heap avec le type défini par l'utilisateur

Répondre

Questions connexes