1 of 8

DS_P4

TA: Chin-Chia Yang

r10942093@ntu.edu.tw

2 of 8

Environment

  • Python = 3.6
  • statistics library is not allowed.

3 of 8

Introduction

  • The following picture shows the files of DS_P4. You should only modify the code in Median.py and do not modify the function names.

​

4 of 8

Median.py

  • Implement MinHeap and MaxHeap
  • We implement the operation and storage of heap by array. You should only modify the TODO parts
  • You can add your own functions, but you have to keep the original functions.
  • Do not import heapq!

5 of 8

Median.py

FindMedian

  • Please return float
  • You have to implement AddNewValues, ShowMedian, RemoveMedian

​

6 of 8

Test your code

  • python3 0001.py
  • python3 0002.py

​

​

7 of 8

  • The testing data to determine your score will contain heap operations(like 0001.py, 0002.py)
  • Your AddNewValues for single item should be O(logn), RemoveMedian should be O(logn), and ShowMedian should be O(1)
  • The maximum number of items could be over 100000, so be aware of your algorithm.

​

Score

8 of 8

Submission

  • Put Median.py in a folder named studentID and compress it to a zip file named studentID.zip (Ex:b08765432.zip)
  • P4 is due 5/19 23:59