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

Question

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

Answer 1

Из Гуавы: MinMaxPriorityQueue,

Answer 2

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

}

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

• https://github.com/m-vahidalizadeh/foundations/blob/master/src/data_structures/MaxHeapWithPriorityQueue.java

• https://github.com/m-vahidalizadeh/foundations/blob/master/src/data_structures/MinHeapWithPriorityQueue.java

Answer 3

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

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

Answer 4

Минимальная куча:PriorityQueue minHeap= new PriorityQueue<>();

Максимальная куча PriorityQueue maxHeap= new PriorityQueue<>(Comparator.reverseOrder());

Answer 5

Ну, вы можете просто передать компаратор, который будет использоваться для сравнения элементов. Это будет полезно, даже если вы хотите отсортировать объекты по некоторым атрибутам. Посмотрите на следующие примеры:

• Минимальная куча:

          PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> a - b);
  

  ---

• Максимальная куча:

          PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b - a);
  

---

• Минимальная куча для объектов

          PriorityQueue<MyObject> pq = new PriorityQueue<>((obj1, obj2) -> obj1.getId() - obj2.getId());
  

---

• Максимальная куча для объектов

          PriorityQueue<MyObject> pq = new PriorityQueue<>((obj1, obj2) -> obj2.getId() - obj1.getId());
  

---

Answer 6

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

Смотрите этот связанный документ.

Тем не менее, не реализует уменьшение или увеличение ключа.

Answer 7

Класс java.util.TreeSet.

Answer 8

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