Implement a Binary Heap in Python

Read about the Binary Heap.

Tasks

Create a new branch in your data structures repository. Call it binheap. You’ll do your work for this assignment in the new branch.

Add a new Python module to your repository. In that file, implement a Binary Heap.

You may choose for yourself whether you want to implement a min-heap or a max-heap. Whichever you choose, be descriptive about it in doc strings and your README.md.

For an additional challenge, implement a heap that can be either and allow the choice to be made at initialization time.

Your heap should support the following public operations:

• push(val): puts a new value into the heap, maintaining the heap property.
• pop(): removes the “top” value in the heap, maintaining the heap property.

You will need to implement some private api in order to support those operations.

The constructor for your heap should default to creating an empty heap, but allow for creating a populated heap given an iterable as an input.

For each feature of your heap, start by writing tests to demonstrate that feature. Then implement the code to pass the tests.

You may use the Python list type as a storage unit for your implementation.

Update your README with information about your implementation of the Binary Heap data type. Include all references and collaborations. It is a requirement that for each method of this data structure, you include in the README a description of its time complexity in Big-O notation! Expect to lose credit if you don’t have this.

Submitting Your Work

When you are finished with your implementation and all tests are passing, create a Pull request from your binheap branch to master. Copy the URL of the new pull request. Submit that URL using the URL input. After you have completed this task, you may merge your branch back to master.

As usual, use the comment feature to submit questions, comments and reflections on the work you did for this assignment.