Java mise en œuvre de Min-Max Tas?

Savez-vous populaire de la bibliothèque (Apache, Google, etc, collections) qui est fiable et Java mise en œuvre pour un min-max tas, qui est un segment qui permet de jeter un regard à son minimum et le maximum de valeur dans O(1) et de supprimer un élément dans O(log n)?

InformationsquelleAutor Yuval Adam | 2009-07-08
  1. 32

    De Goyave: MinMaxPriorityQueue.

    • En particulier, depuis la première question posée à propos de google-collections, qui est maintenant à la Goyave.
    • le seul petit inconvénient est le manque de standard Deque mise en œuvre
    • Il n'est pas satisfait de la Deque contrat, de sorte que fonctionne comme prévu.
    • pourriez-vous préciser pourquoi? La seule difficulté que je suis capable de voir, c'est la mise en œuvre de Deque#removeFirstOccurrence() et removeLastOccurence() en raison de la nature instable de min-max tas
    • Non, le problème est que les deques devez rester dans l'ordre que vous mettez dans les éléments. Par exemple, la documentation de Deque spécifie que lorsqu'il est utilisé comme une file d'attente FIFO résultats du comportement. MinMaxPriorityQueue pourrait techniquement de mettre en œuvre les méthodes, mais il ne pouvait pas satisfaire le contrat.
    • Après avoir jeté un bref coup d'oeil à la Goyave est MinMaxPriorityQueue code source, j'ai réalisé qu'il n'implémente pas un "vrai" min-max tas (dont très peu de gens le savent), mais plutôt simplement, il met en œuvre un double clos file d'attente de priorité à l'aide de deux tas, un min-tas et un max-heap, qui sont mis ensemble.

    InformationsquelleAutor Louis Wasserman
  2. 25

    Au lieu d'un max-min tas, pourriez-vous utiliser deux instances d'un java.util.PriorityQueue contenant les mêmes éléments? La première instance est passé un comparateur qui met le maximum à la tête, et le deuxième exemple serait d'utiliser un comparateur qui met le minimum à la tête.

    L'inconvénient est que, d'ajouter, supprimer, etc devraient être effectuées sur les deux structures, mais il devrait répondre à vos exigences.

    • +1. C'est une bonne réponse aux exigences énoncées à coup d'oeil à l'origine en O(1) et le retirer en O(log.n). Notez cependant qu'une PriorityQueue ne pas mettre en œuvre toutes les opérations segment (par exemple, decreaseKey, increaseKey).
    • Notez que le non-argument remove(), ce qui enlève de la tête de la file d'attente, est O(log(n)), alors que remove(Object o), est O(n). Référence: docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html
    • Downvoted parce que le retrait ne sera pas en O(log n) plus. Retrait de la minimale à partir de l'une des files d'attente est O(log n), mais de supprimer le point identiques, qui sera à la fin de l'autre file d'attente, est O(n).
    • C'était ma pensée, mais j'ai réalisé que nous pouvions encore faire les deux tas de solution de travail de la manière suivante. Quand nous avons extrait/peek max, nous ne faisons que de la max-tas, et vice versa pour min tas. Ceci, bien sûr, les résultats de deux incompatible tas. Nous gardons la trace de la dernière max extrait et la dernière min extrait, de sorte que quand ils coïncident, la structure de données est vide. Cela fonctionnerait si nous n'avons pas besoin d'appuyer l'insertion et les principaux changements (après l'extraction a été fait), que l'OP n'a pas de spécifier des exigences.
    InformationsquelleAutor Il-Bhima
  3. 17

    Java a de bons outils afin de mettre en œuvre min et max des tas. Ma suggestion est d'utiliser la file d'attente de priorité structure de données afin de mettre en œuvre ces tas. Pour la mise en œuvre de max tas avec file d'attente de priorité essayez ceci: 

    import java.util.PriorityQueue;

public class MaxHeapWithPriorityQueue {

    public static void main(String args[]) {
        //create priority queue
        PriorityQueue<Integer> prq = new PriorityQueue<>((x,y) -> y-x);

        //insert values in the queue
        prq.add(6);
        prq.add(9);
        prq.add(5);
        prq.add(64);
        prq.add(6);

        //print values
        while (!prq.isEmpty()) {
            System.out.print(prq.poll()+" ");
        }
    }

}

    Pour la mise en œuvre de la min tas avec file d'attente de priorité, essayez ceci:

    import java.util.PriorityQueue;

public class MinHeapWithPriorityQueue {

    public static void main(String args[]) {
        //create priority queue
        PriorityQueue< Integer > prq = new PriorityQueue <> ();

        //insert values in the queue
        prq.add(6);
        prq.add(9);
        prq.add(5);
        prq.add(64);
        prq.add(6);

        //print values
        while (!prq.isEmpty()) {
            System.out.print(prq.poll()+" ");
        }
    }

}

    Pour plus d'informations, veuillez visiter:

    • Il est plus pratique d'utiliser Collections.reverseOrder() comme un argument de PriorityQueue dans MaxHeap classe.
    • Qu'entendez-vous par plus commode? Pourriez-vous nous expliquer plus?
    • Je pense que reverseOrder méthode est plus facile à lire et à comprendre ce qu'il fait en comparant à (x,y) -> y-x
    • Michael, comme je l'ai fait il, est la manière proposée par Oracle. Oracle a suggéré d'utiliser un Comparateur. Veuillez jeter un oeil à ce lien: docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html
    • Collections.reverseOrder() renvoie également un Comparateur. De sorte qu'il peut être utilisé dans la PriorityQueue constructeur. Les deux méthodes de travail. Mais pour moi reverseOrder est de plus en plus évidente. C'est tout.
    • Pour cette partie, j'ai utilisé une expression lambda (Java 8). Cependant, ceci est basé sur la préférence. Votre suggestion est bonne aussi. Je vous remercie de votre alternative.
    • Dans l'Expression Lambda, la comparaison par soustraction truc qui pourrait être facilement cassé en raison de débordement d'entier. Plaine comparaison est suggéré: (x, y) -> x < y ? -1 : x == y ? 0 : 1

    InformationsquelleAutor Vahid
  4. 2

    Comment sur com.aliasi.util.MinMaxHeap? Cela fait partie de LingPipe; malheureusement, la licence peut-être un problème.

    Voir ce document lié.

    Ne pas mettre en œuvre decreaseKey ou increaseKey, si.

    InformationsquelleAutor NamshubWriter
  5. 0

    La java.util.TreeSet classe.

    • J'ai besoin d'aide pour les valeurs en double... Ensemble est "un peu" problématique dans cet aspect.
    • -1 TreeSet implémente la plupart des opérations en O(log n) - l'exigence était de jeter un oeil à minimum et maximum en O(1).
    • TreeSet également ne pas avoir une decreaseKey ou increaseKey opération, qui est l'un des définitive des opérations d'un segment. Voir en.wikipedia.org/wiki/Heap_(data_structure)
    • Si vous avez besoin de l'appui des valeurs en double, vous pouvez utiliser TreeBag (commons.apache.org/collections/api-release/org/apache/commons/...) à partir de Apache Commons Collections, ou TreeMultiset (google-collections.googlecode.com/svn/trunk/javadoc/com/google/...) à partir de Google Collections. Si vous avez besoin de increaseKey ou decreaseKey, vous pouvez simplement supprimer l'élément et l'ajouter de nouveau.
    • Ou utiliser un TreeMap que les cartes clés pour compte. TreeSet est réellement mis en œuvre avec un TreeMap sous le capot.
    • -1. TreeSet/TreeMap est un rouge-noir arbre, pas un tas.
    • les valeurs en double et stable de la commande peut être mis en œuvre par le remplacement d'une clé par [key, stamp] paire, donc la comparaison est effectuée sur la touche, puis sur le timbre. Cependant, TreeSet n'est pas un remplacement de max-min tas deque.

    InformationsquelleAutor Nat