Реализация MinHeap и MaxHeap в Java

Question

Я хочу знать, есть ли в java какая-либо коллекция, которая может помочь мне в реализации minheap и maxheap Я знаю, что могу использовать структуру данных PriortyQueue для реализации maxheap. Можем ли мы использовать то же самое для minheap? Если да, то как?

Спасибо, Manan

Answer 1

Я думаю, что у вас все наоборот: куча - это способ реализации очереди с приоритетами. Что касается минимальной / максимальной части, просто напишите соответствующие Comparator классы.

Answer 2

В этом у вас уровень абстракции немного задом наперед.

Куча - это древовидная структура (обратите внимание, что на самом деле ей не нужно иметь дерево, а скорее метод связи точек данных со своими «потомками» (подробнее см. Ниже)) структура данных, которая имеет очень специфическое отношение между узлами и их дочерними элементами.

Очередь приоритетов, напротив, является более абстрактной идеей. Это очередь (список, похожий на структуру данных с моделью доступа к данным FIFO), но вместо того, чтобы быть фактически FIFO, он сначала возвращает объект с наибольшим приоритетом.

Точно так же, как в куче, есть разные способы реализации базовой структуры, поэтому в очереди с приоритетами можно делать много разных вещей. Преимущество использования кучи в качестве базовой структуры очереди с приоритетами заключается в том, что вам больше не нужно выполнять работу. Просто сложите значения в зависимости от их приоритета, и когда кто-то запросит значение, верните голову.

Основное различие заключается в том, что куча определяется ее древовидным свойством и ограничением кучи, где приоритетная очередь определяется только тем, как она взаимодействует с другими.

// A note on creating heaps
// Given that A is an array of n values indexed from 1 to n
// We can model a tree like structure buy stating that for any
// value i in (1,n) it's children are 2 * i and 2 * i + 1
// So with an array you can easily model a heap in this manner