Как лучше всего реализовать PriorityQueue в java?

Я пытаюсь реализовать свой собственный класс PriorityQueue с нуля (без использования каких-либо существующих импортов или библиотек Java). Я знаю, что хочу использовать структуру данных с минимальной кучей. Но я визуализирую кучу как форму в двоичном дереве поиска. Должен ли я использовать узлы в стиле связанного списка для реализации этой минимальной кучи, или мне следует использовать массив? Каковы преимущества или предпочтительный метод любого из них? Или есть третий доступный вариант, который я мог бы использовать?


java heap priority-queue min-heap
person devwraps    schedule 28.04.2017    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Прежде чем ответить на вопрос, посмотрите это.

Но я визуализирую кучу как форму в двоичном дереве поиска.

Это неправда. Куча — это форма двоичного дерева, но не двоичного дерева поиска. См. Разницу между двоичным деревом и двоичным деревом поиска

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

Дан n - это индекс текущего узла, а индекс начинается с 1 (для простоты)

  • индекс родителей = n/2
  • левый дочерний индекс = 2n
  • правый дочерний индекс = 2n+1

Когда вы делаете это с помощью LinkedList.get(n), это O(n). В ArrayList или массиве это O (1).

person exiter2000    schedule 28.04.2017

arrow_upward
0
arrow_downward

Самая простая реализация, о которой я могу думать, будет использовать LinkedList или ArrayList, которые сохраняют себя в отсортированном порядке на основе приоритета. Затем вы удаляете из начала или из конца списка (в зависимости от того, как вы сортируете массив), когда пришло время удалить кого-то из очереди.

person victor    schedule 28.04.2017