Courses‎ > ‎APCS - Term 1‎ > ‎Konstantinovich‎ > ‎

2019-04-30 Medians

posted Apr 30, 2019, 5:51 AM by Konstantinovich Samuel   [ updated Apr 30, 2019, 6:31 AM ]
Goal: Utility of heaps

Do Now:
If you wanted to make a data structure with the following public methods:
  void add(double) - insert the value into the data structure
  double getMedian()  - return the median of all of the values that have been added to the data structure. (do not remove anything) 

getMedian() MUST run in O(1)

-What is the naive way of accomplishing this? [using a simple data structure you already have]
-What is the speed of the add operation?
-How can you make this operations faster?


Exam Next Friday:
  Multiple choice only
  General java stuff (studied already for the AP)
    Including a focus on:
      +Heaps 
      +Trees
    Excluding:
      -Stacks
      -Queues


Comments