Skip to content

Implement running median #3

@palemium

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

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