Skip to content
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

Implement a heap-based priority queue #13

Open
10 tasks
mwermelinger opened this issue Jan 7, 2024 · 0 comments
Open
10 tasks

Implement a heap-based priority queue #13

mwermelinger opened this issue Jan 7, 2024 · 0 comments
Labels
effort: high These issues require the most work priority: medium type: feature New feature

Comments

@mwermelinger
Copy link
Member

A min/max-priority queue can be implemented with a min/max-heap. (Section 16.6 in the M269 book.)

In subfolder paddles:

  • Create a file priority_queue.py with a docstring explaining the Priority Queue ADT.
  • Write a class HeapMinPriorityQueue that implements a min-priority queue with a binary heap, represented as a Python list.
  • The __init__ method has a parameter with the priority-item pairs to be added to the queue (the parameter is of type collections.abc.Iterable[tuple].
  • The inspector methods are:
    • return the front of the queue (item and corresponding priority)
    • return the size of the queue
  • The modifier methods are:
    • enqueue a given item with a given priority
    • dequeue the next item and its priority (lowest value of all priorities)
  • Add a heapsort function to sorting.py.

In subfolder tests:

  • Create a file test_priority_queue.py that tests the modifier methods.
@mwermelinger mwermelinger added effort: high These issues require the most work priority: medium type: feature New feature labels Jan 7, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
effort: high These issues require the most work priority: medium type: feature New feature
Projects
None yet
Development

No branches or pull requests

1 participant