pydatastructs
pydatastructs copied to clipboard
Add Priority Queues to Linear Data Structures
The PyDataStructs library currently supports various linear data structures, but Priority Queues are missing. A Priority Queue is an important data structure where each element has a priority, and elements are dequeued based on their priority (highest or lowest priority first).
Proposed Implementation Implement Min-Priority Queue and Max-Priority Queue using a Heap (Binary Heap, Fibonacci Heap, or Binomial Heap). Support basic operations: insert(element, priority) get_highest_priority() or get_lowest_priority() extract_highest_priority() or extract_lowest_priority() increase_priority() or decrease_priority() delete(element) Provide a Pythonic and clean API for consistency with the existing data structures. Ensure efficient implementation with logarithmic time complexity (O(log n)) for insertion and deletion. Write test cases to maintain high test coverage. Use Cases Graph Algorithms: Used in Dijkstra's and Prim’s algorithms. Scheduling: Process/task scheduling in operating systems. Event-Driven Simulations: Managing events based on priority. References for Implementation Introduction to Algorithms (CLRS) - Chapter on Heaps and Priority Queues Open Data Structures - https://opendatastructures.org/ Additional Information The implementation should follow the contribution guidelines of PyDataStructs. The code should be well-documented and include examples demonstrating usage. Test the implementation using pytest. Would love to hear feedback from the maintainers on this proposal!
@tiwariar7 It is already implemented in miscellaneous_data_structures\queue.py..