Skip to content

Add Priority Queues to Linear Data Structures #638

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
tiwariar7 opened this issue Mar 12, 2025 · 1 comment
Open

Add Priority Queues to Linear Data Structures #638

tiwariar7 opened this issue Mar 12, 2025 · 1 comment

Comments

@tiwariar7
Copy link

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!

@asmit27rai
Copy link

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants