¿Cómo se diseñaría una estructura de datos para soportar las siguientes operaciones en tiempo logarítmico: insert, deleteMin, deleteMax findMin, findMax?

Para esto existe una estructura de datos: un árbol de búsqueda binario.

Esta es una estructura de datos de la siguiente forma:

escriba SearchTree a = Nodo a (SearchTree a) (SearchTree a)
El | Vacío

Con eso, y suponiendo que a es un tipo ordenado, podemos escribir un procedimiento de insert como este:

insert :: (Ord a) => SearchTree a -> a -> SearchTree a
inserte [correo electrónico protegido] (Nodo x izquierda derecha) y
El | x El | x> y = Nodo x (insertar izquierda y) derecha
El | de lo contrario = árbol
insert Empty y = Nodo y Empty Empty

Ahora que establecimos la estructura de nuestro árbol, findMin y findMax ahora son fáciles.

Para encontrar el mínimo, solo sigue el lado izquierdo del árbol hasta que no puedas ir más lejos:

findMin (Ord a) => SearchTree a -> Quizás a
findMin (Node x Empty _) = Some x
findMin (Nodo x left _) = findMin left
findMin Empty = Nothing

Ahora puede findMax por findMax , por lo que en lugar de ir a la izquierda, deberá seguir a la derecha. El código generalmente será el mismo para ambos.

La eliminación será un poco más complicada, ya que necesitaremos empalmar a todos los hijos que nuestro nodo menor o mayor tenga con su padre, o terminaremos perdiendo fragmentos enteros de nuestra estructura de datos que no teníamos la intención de eliminar.

deleteMin terminaría luciendo así:

deleteMin :: (Ord a) => SearchTree a -> SearchTree a
deleteMin Empty = Empty
deleteMin (Nodo _ Empty right) = right
deleteMin (Nodo x izquierda derecha) = Nodo x (deleteMin izquierda) derecha

Aquí seguimos el lado izquierdo todo el camino hacia la izquierda, y “eliminamos” el nodo mínimo simplemente reemplazándolo por su hijo derecho. deleteMax sería lo mismo, solo con las direcciones invertidas.

Ahora imagino que todavía estás aprendiendo, y la pregunta que planteaste sería algo que haría un estudiante perplejo, por lo que simplemente publicar el enlace de Wikipedia en árboles de búsqueda binarios no hubiera sido suficiente; Necesitabas un código que te ayudara a comprender parte de la estructura. Aprender a arborizar es complicado, pero vale la pena el esfuerzo.

Pero eso no responde exactamente por qué lo hice en Haskell. Es extremadamente improbable que esté aprendiendo a programar con Haskell, y habría encontrado ejemplos de Python o Java más esclarecedores. Lo hice de esta manera para no ayudarte a hacer trampa en tu tarea.

Un BST equilibrado lo haría. En Java, la clase TreeSet (un árbol negro rojo) es compatible con todas las operaciones mencionadas anteriormente.

TreeSet t = new TreeSet ();
t.primero (); // min
t.last (); // max
t.pollFirst (); // del min
t.pollLast (); // del max

La solución de dos pilas no funcionará porque cuando elimina un elemento, debe eliminarlo de ambos montones. La operación deleteMin, por ejemplo, llevará tiempo logarítmico en el montón mínimo pero en el montón máximo. primero debe buscar el artículo y eso lleva tiempo lineal.

Lo mejor es seguir con los árboles estándar: árbol AVL, árbol rojo-negro, árbol 2–3, árbol 2–3–4, etc.

Un montón binario sería el camino a seguir. Find min y find max serían operaciones de tiempo constante en un montón mínimo y un montón máximo, respectivamente.

La eliminación será una operación de registro.

Esto se debe a que en un montón min / max el elemento min / max está en la parte superior.

En caso de inserción o eliminación, el montón tendría que ser reordenado y eso podría tomar un número logarítmico de pasos en un montón binario. Hay ventajas de usar otros tipos de montones, por ejemplo, el montón de Fibonacci para el mismo.

¿Te importa el orden de la estructura?

Por ejemplo, en la inicialización, tengo algo como [4, 7, 9 1, 3, 5, 2]

¿Te importa el orden cuando manipulamos la lista más tarde? ¿Desea mantener el mismo orden, o la lista se puede ordenar en el momento de la inicialización y seguir ordenándose todo el tiempo después?

Creo que debería ser posible crear un montón en una lista de modo que siempre mantenga el mínimo en la parte delantera y el máximo en la parte posterior y cumpla con todas estas restricciones. Realmente no he hecho un estudio concertado para ver cómo se podría hacer, pero como me lo preguntaste, tal vez lo derribaré y lo resolveré.

Pero tiene razón en que usar dos montones de punteros para los mismos objetos funcionará bien para los requisitos de tiempo. El único inconveniente es usar el doble de espacio. (No está en el lugar como un único montón binario puede ser).