pydatastructs icon indicating copy to clipboard operation
pydatastructs copied to clipboard

Add Priority Queues to Linear Data Structures

Open tiwariar7 opened this issue 8 months ago • 1 comments

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 avatar Mar 12 '25 14:03 tiwariar7

@tiwariar7 It is already implemented in miscellaneous_data_structures\queue.py..

asmit27rai avatar Mar 17 '25 13:03 asmit27rai