Реализация Java для Min-Max Heap?

Знаете ли вы о популярной библиотеке (Apache, Google и т.д.), которая имеет надежную реализацию Java для кучи min-max, которая представляет собой кучу, которая позволяет заглядывать ее минимальное и максимальное значение в O(1) и для удаления элемента в O(log n)?

Ответ 1

Из Guava: MinMaxPriorityQueue.

Ответ 2

Вместо кучи max-min вы могли бы использовать два экземпляра java.util.PriorityQueue, содержащий те же элементы? Первый экземпляр будет передан компаратором, который ставит максимум в голову, а второй экземпляр будет использовать компаратор, который ставит минимум в голову.

Недостатком является то, что добавление, удаление и т.д. должно выполняться на обеих структурах, но оно должно удовлетворять вашим требованиям.

Ответ 3

В Java есть хорошие инструменты для реализации минимальных и максимальных куч. Мое предложение использует структуру данных очереди приоритетов, чтобы реализовать эти кучи. Для реализации максимальной кучи с приоритетной очередью попробуйте следующее:

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

}

Для реализации мини-кучи с приоритетной очередью попробуйте следующее:

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

}

Для получения дополнительной информации посетите:

Ответ 4

Как насчет com.aliasi.util.MinMaxHeap? Это часть LingPipe; к сожалению, проблема может быть проблемой.

См. эту связанную статью.

Не реализует reduceKey или IncreKey, хотя.

Ответ 5

класс java.util.TreeSet.

Ответ 6

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;
}