Estoy tratando de implementar mi propia clase PriorityQueue desde cero (sin usar ninguna importación o biblioteca de Java existente). Sé que quiero usar una estructura de datos de montón mínimo. Pero visualizo un montón como un formulario en Binary Search Tree. ¿Debería usar nodos de estilo de lista enlazada para implementar este montón mínimo, o debería usar una matriz? ¿Cuáles son los beneficios o el método preferido de cualquiera? ¿O hay una tercera opción disponible que podría usar?
Antes de responder a la pregunta, por favor vea esto.
Pero visualizo un montón como un formulario en Binary Search Tree.
Esto no es verdad. Heap es una forma de árbol binario, pero no un árbol de búsqueda binario. Consulte la diferencia entre el árbol binario y el árbol de búsqueda binaria
Ahora, para responder a su pregunta, elegiría algún tipo de forma de matriz. La razón es que necesito calcular mis hijos o mi padre con información de índice con frecuencia cuando implemento un montón. Por lo general, sucede con el siguiente cálculo.
Dado que n es el índice del nodo actual y el índice comienza desde 1 (por simplicidad)
Cuando haces esto con LinkedList.get(n), es O(n). En ArrayList o array, es O(1).
La implementación más fácil que se me ocurre sería usar una LinkedList o ArrayList que se mantenga ordenada según la prioridad. Luego, elimina del frente o de la parte posterior de la lista (dependiendo de cómo ordene la matriz) cuando sea el momento de eliminar a alguien de la cola.