You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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!
The text was updated successfully, but these errors were encountered:
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!
The text was updated successfully, but these errors were encountered: