Structure de segment de recherche consultable

Question

Le problème consiste à accéder à une série de valeurs par deux méthodes différentes. D'abord, par priorité; cela est implémenté assez simplement avec un tas. En outre, il doit être possible de "marquer" chaque valeur avec un ou plusieurs symboles à travers lesquels une liste d'éléments peut être accédée.

Cela serait assez facile à mettre en œuvre efficacement en référençant les mêmes données dans deux structures différentes. Cependant, ceux-ci doivent former une file d'attente cohérente. Par conséquent, les éléments retirés à travers une structure doivent également être retirés de l'autre, une opération pour laquelle un tas n'est pas extrêmement approprié. Y a-t-il une structure de données qui est capable de fournir une commande efficace d'une valeur (idéalement optimisée pour pousser/éclater), sans dégrader complètement la performance de trouver/supprimer des nœuds à des emplacements arbitraires?

Answer 1

Vous pouvez supprimer n'importe quel élément d'un tas binaire en O (log (n)) si vous savez lequel supprimer. N'importe quel nœud peut être traité comme un sous-tas valide et vous pouvez utiliser l'opération delete-max (ou delete-min) exactement comme vous le feriez pour l'ensemble.

Le seul problème est comment savoir lequel supprimer? Je pense que j'ai une solution pour ça. Utilisez un wrapper pour la classe stockée qui fait référence à son noeud de segment et supprimez ce noeud du destructeur de wrappers. Lorsque vous voulez supprimer un élément de la collection, vous pouvez simplement supprimer l'encapsuleur à l'aide de l'un des index et il s'occupera du reste. Lorsque vous insérez un élément dans la collection, vous devez créer un objet wrapper et transmettre une référence à son noeud de segment.

Voici un code C++:

template <class T> class Wrapper { 
    T data; 
    HeapNode* index_heap; 
    Foo* index_tags; 
    Bar* index_queue; 

    public: ~Wrapper() { 
     index_heap->delete_max(); 
     index_tags->delete_foo(); 
     index_queue->delete_bar(); 
    } 
};