7
¿Hay alguna implementación de cola de prioridad confiable y simple (lista de enlaces preferida, no necesaria) para C?Implementación de cola de prioridad en C
Más en general, ¿qué librerías estándar C usas?
A
Respuesta
0
Echa un vistazo PQLib.
Utilizo las bibliotecas estándares C estándar. ;)
+10
Por favor, lea POR FAVOR el archivo LICENSE en PQLib _very_ cuidadosamente. Reintroduce un nuevo tipo de cláusula publicitaria (incluso peor que la cláusula publicitaria BSD original) y es incompatible con la GPL/LGPL (todas las versiones). Básicamente, no puede vincular againtst glibc y PQLib y distribuir legalmente el producto final. La biblioteca es decididamente _no_ de código abierto, y mucho menos de software libre. –
+1
@Tim No me di cuenta ... dice BSD, pero deben significar BSD especial. +1 – WhirlWind
+0
NO USE PQLIB. No está completo y no funciona. – Mark
3
Tengo una cola de prioridad escrita en C, alojada en el código de google. licencia MIT
https://code.google.com/p/pqueue-heap-c/source/browse/trunk/pqueue.cpp
El código ha sido utilizado en algunos proyectos por lo que es sólido, pero lo escribió en el 98, así que no recuerdo cómo usarlo. No se deje engañar por la extensión cpp. Es directo C.
+1
El código necesita un poco de limpieza pero funciona bien, ¡gracias! – congusbongus
+0
¿Qué proyectos han usado tu código? ¡Gracias por hacer y compartir esto! – Darakian
+0
De nada @Darakian Utilicé esto en algún código de búsqueda de ruta en un videojuego hace mucho tiempo a finales de los 90. – justinhj
4
El source code que acompaña Robert Sedgewick 's Algorithms in C, Parts 1-4 (Fundamental Algorithms, Data Structures, Sorting, Searching) contiene una implementación basada en el montón y una lista. Consulte el Capítulo 9: Colas de prioridad y Heapsort.
2
PQLib (la corriente respuesta aceptada) es incompleta y la funcionalidad no coincide con la documentación a partir de esta publicación. Por ejemplo, la documentación pq_dequeue dice que devuelve una entrada. La implementación devuelve NULL. Hay muchos comentarios "HACER" en el código, como "eliminar el nodo que contiene la entrada de mayor prioridad de su pila". La lógica esencial falta.
Para cualquiera que busque una cola de prioridad: Recomiendo encontrar algún código que tenga buenas pruebas de unidad de paso. No recomiendo PQLib a menos que esté actualizado e incluya pruebas.
Para el propietario de PQLib o cualquiera que lo recomiende: asumí que este código estaba completo y pasé bastante tiempo depurándolo hasta que me di cuenta de que no era así, lo cual fue frustrante. No recomiende el código que no ha probado o sabe que es un trabajo en progreso.
+0
¡Sí, acabo de perder una hora, debería haber leído un poco más de este hilo! – Mark
Cuestiones relacionadas
- 1. C# cola de prioridad
- 2. Implementación de cola de prioridad de Brodal
- 3. Implementación de cola en C#
- 4. Java: cola de prioridad
- 5. Cola de prioridad concurrente en .NET 4.0
- 6. Implementación de una cola de prioridad que se puede iterar en C++
- 7. Cambiar la prioridad en una cola de prioridad personalizada
- 8. ¿Estructura de cola de prioridad utilizada?
- 9. Servicio con cola de prioridad en Android
- 10. ¿Hay implementación de estructura de datos de cola de prioridad en la biblioteca estándar de Ruby?
- 11. método de limpieza de cola de prioridad
- 12. Cola de prioridad eliminar tiempo de complejidad
- 13. Cola de prioridad de doble terminación
- 14. Par dentro de la cola de prioridad
- 15. Base de datos de la Cola de prioridad
- 16. Cola de prioridad con prioridades de elementos dinámicos
- 17. ¿Tiene R una cola de prioridad como PriorityQueue de Java?
- 18. ¿Java tiene una cola de prioridad mínima indexada?
- 19. Cola de prioridad con una función de búsqueda - Implementación más rápida
- 20. Interrumpir el tie en una cola de prioridad usando python
- 21. Comparación de implementaciones de cola de prioridad en Haskell
- 22. ¿Cómo implementar una cola de prioridad de multiprocesamiento en Python?
- 23. cola de prioridad de pares en orden inverso
- 24. Cola de prioridad de STL en la clase personalizada
- 25. cola de prioridad de STL - eliminar un elemento
- 26. Repriorización de la cola de prioridad (manera eficiente)
- 27. Implementación de una cola basada en archivos
- 28. Eliminación de un elemento arbitrario de la cola de prioridad
- 29. Microsoft Message Queue: indicador de prioridad o una cola separada?
- 30. Cola de prioridad de Java con un comparador anónimo personalizado
¿Por qué quieres decir con "qué bibliotecas estándar?" – WhirlWind
Me gusta implementar mis PQs sobre montones binomiales. –