Каков наилучший способ реализовать PriorityQueue в Java?

Question

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

Answer 1

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

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

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

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

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

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

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

Answer 2

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