Vraag Java-implementatie voor Min-Max Heap?


Kent u een populaire bibliotheek (Apache, Google, enz., Collecties) die een betrouwbare Java-implementatie heeft voor een min-max-heap, dat is een heap waarmee u de minimum- en maximumwaarde ervan kunt bekijken in O(1) en om een ​​element in te verwijderen O(log n)?


32
2017-07-08 14:02


oorsprong


antwoorden:


Van Guava: MinMaxPriorityQueue.


30
2018-02-02 20:45



In plaats van een max-min-heap, kunt u twee exemplaren van een java.util.PriorityQueue met dezelfde elementen? De eerste instantie zou een comparator passeren die het maximum aan het hoofd zet, en de tweede instantie zou een comparator gebruiken die het minimum aan het hoofd zet.

Het nadeel is dat toevoegen, verwijderen, enz. Op beide structuren zou moeten worden uitgevoerd, maar het zou aan uw vereisten moeten voldoen.


23
2017-07-08 14:26



Java heeft goede hulpmiddelen om min en max hopen te implementeren. Mijn suggestie is om de gegevensstructuur van de prioritaire wachtrij te gebruiken om deze stapels te implementeren. Voor de uitvoering van de max-heap met prioritaire wachtrij, probeer dit:

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()+" ");
        }
    }

}

Voor het implementeren van de min-heap met prioritaire wachtrij, probeert u dit:

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()+" ");
        }
    }

}

Ga voor meer informatie naar:


15
2017-09-24 21:51



Wat dacht je van com.aliasi.util.MinMaxHeap? Dit is onderdeel van LingPipe; Helaas, de licentie kan een probleem zijn.

Zien dit gerelateerde artikel.

Implementeert echter geen reductionKey of increaseKey.


2
2017-07-08 14:25



De java.util.TreeSet klasse.


0
2017-07-08 14:03



private void heapifyUp(int current) {
int parent = (current - 1) / 2;
if (current < 0)return;
while (current > 0 && arr[current] > arr[parent]) {
   int temp = arr[parent];
   arr[parent] = arr[current];
   arr[current] = temp;
   current = parent;
  parent = (current - 1) / 2;
 } return;
}

-8
2017-08-17 05:13