Ir a una cola de prioridad multicapa

Answer

1. 

   davy.ai

   August 5, 2023 at 9:55 pm

   No estoy consciente de ningún paquete incorporado en Go que proporcione una cola de prioridad multinivel. Sin embargo, podemos crear nuestra propia implementación de una cola de prioridad multinivel utilizando el paquete container/heap y definiendo nuestras propias estructuras de datos y funciones personalizadas. Aquí hay un enfoque posible para implementar una cola de prioridad multinivel:

   1. Defina una estructura para representar una calificación de curso, incluyendo el nombre del estudiante, el nombre del curso y la calificación.

   type calificacion struct {
       estudiante string
       curso  string
       calificación   int
   }
   

   1. Defina una lista de objetos calificacion y una función para obtener las mejores N calificaciones de esa lista utilizando una cola de prioridad.

   type heapCalificacion []calificacion
   
   func (h heapCalificacion) Len() int           { return len(h) }
   func (h heapCalificacion) Less(i, j int) bool { return h[i].calificación > h[j].calificación }
   func (h heapCalificacion) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
   
   func (h *heapCalificacion) Push(x interface{}) {
       *h = append(*h, x.(calificacion))
   }
   
   func (h *heapCalificacion) Pop() interface{} {
       antiguo := *h
       n := len(antiguo)
       x := antiguo[n-1]
       *h = antiguo[0 : n-1]
       return x
   }
   
   func obtenerMejoresCalificaciones(calificaciones []calificacion, n int) map[string][]int {
       h := &heapCalificacion{}
       heap.Init(h)
   
       for _, calificacion := range calificaciones {
           heap.Push(h, calificacion)
           if h.Len() > n {
               heap.Pop(h)
           }
       }
   
       resultado := make(map[string][]int)
       for h.Len() > 0 {
           calificacion := heap.Pop(h).(calificacion)
           resultado[calificacion.curso] = append(resultado[calificacion.curso], calificacion.calificación)
       }
   
       return resultado
   }
   

   1. Defina una estructura para representar un curso, incluyendo el nombre del curso y la lista de calificaciones para ese curso.

   type curso struct {
       nombre  string
       calificaciones []calificacion
   }
   

   1. Defina una lista de objetos curso y una función para obtener los mejores N cursos con las calificaciones más altas utilizando una cola de prioridad multinivel.

   type heapCurso []curso
   
   func (h heapCurso) Len() int           { return len(h) }
   func (h heapCurso) Less(i, j int) bool { return h[i].calificaciones[0].calificación > h[j].calificaciones[0].calificación }
   func (h heapCurso) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
   
   func (h *heapCurso) Push(x interface{}) {
       *h = append(*h, x.(curso))
   }
   
   func (h *heapCurso) Pop() interface{} {
       antiguo := *h
       n := len(antiguo)
       x := antiguo[n-1]
       *h = antiguo[0 : n-1]
       return x
   }
   
   func obtenerMejoresNCursos(cursos []curso, n int) map[string][]int {
       h := &heapCurso{}
       heap.Init(h)
   
       for _, curso := range cursos {
           calificaciones := curso.calificaciones
           if len(calificaciones) > n {
               calificaciones = calificaciones[:n]
           }
           mejoresCalificaciones := obtenerMejoresCalificaciones(calificaciones, n)
           for _, puntajes := range mejoresCalificaciones {
               suma := 0
               for _, puntaje := range puntajes {
                   suma += puntaje
               }
               puntajePromedio := suma / len(puntajes)
               heap.Push(h, curso{nombre: curso.nombre, calificaciones: puntajes})
               if h.Len() > n {
                   heap.Pop(h)
               }
           }
       }
   
       resultado := make(map[string][]int)
       for h.Len() > 0 {
           curso := heap.Pop(h).(curso)
           resultado[curso.nombre] = curso.calificaciones
       }
   
       return resultado
   }
   

   Usando estas funciones, podemos obtener los mejores N cursos con las calificaciones más altas para los mejores N estudiantes con las calificaciones más altas de la siguiente manera:

   // Datos de ejemplo
   calificaciones := []calificacion{
       {estudiante: "Alice", curso: "Matemáticas", calificación: 95},
       {estudiante: "Bob", curso: "Matemáticas", calificación: 90},
       {estudiante: "Charlie", curso: "Matemáticas", calificación: 85},
       {estudiante: "David", curso: "Matemáticas", calificación: 80},
       {estudiante: "Eve", curso: "Matemáticas", calificación: 75},
       {estudiante: "Alice", curso: "Física", calificación: 90},
       {estudiante: "Bob", curso: "Física", calificación: 85},
       {estudiante: "Charlie", curso: "Física", calificación: 80},
       {estudiante: "David", curso: "Física", calificación: 75},
       {estudiante: "Eve", curso: "Física", calificación: 70},
       {estudiante: "Alice", curso: "Química", calificación: 85},
       {estudiante: "Bob", curso: "Química", calificación: 80},
       {estudiante: "Charlie", curso: "Química", calificación: 75},
       {estudiante: "David", curso: "Química", calificación: 70},
       {estudiante: "Eve", curso: "Química", calificación: 65},
   }
   
   cursos := []curso{
       {nombre: "Matemáticas", calificaciones: calificaciones[:5]},
       {nombre: "Física", calificaciones: calificaciones[5:10]},
       {nombre: "Química", calificaciones: calificaciones[10:]},
   }
   
   // Obtener los 2 mejores cursos con las calificaciones más altas para los 3 mejores estudiantes con las calificaciones más altas
   resultado := obtenerMejoresNCursos(cursos, 2)
   fmt.Printf("%v\n", resultado)
   
   // Salida:
   // map[Matemáticas:[95 90] Física:[90 85] Química:[85 80]]
   

   Cabe destacar que la función obtenerMejoresNCursos solo recupera los mejores N cursos con las calificaciones más altas para cada estudiante por separado, y no garantiza que esos cursos también estén en los mejores N en general. Si queremos recuperar cursos que estén entre los mejores N en general, independientemente de qué estudiantes hayan tomado esos cursos, tendríamos que modificar la implementación en consecuencia.

Comments are closed.