Skip to content

Implement running median #3

Description

@palemium

Step 1: Add next item to one of the heaps

if next item is smaller than maxHeap root add it to maxHeap,
else add it to minHeap

Step 2: Balance the heaps (after this step heaps will be either balanced or
one of them will contain 1 more item)

if number of elements in one of the heaps is greater than the other by
more than 1, remove the root element from the one containing more elements and
add to the other one
Then at any given time you can calculate median like this:

If the heaps contain equal amount of elements;
median = (root of maxHeap + root of minHeap)/2
Else
median = root of the heap with more elements

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions