Goal: Compute median of data which is changing.
Median: The median is the value separating the higher half of a data from the lower half.
Steps involved in computing median would be to sort the data and then find the mid point. Best sorting Algorithm can give us O(N Log N), a linearithmic solution. This can be expensive for large datasets if data is added/removed frequently.
Binary Heap is a very useful data structure for this purpose mainly because of its support in O(log N) for insert/deletion. It achieves this due to its logical representation of being a complete and balanced binary tree.
Following is the code for doing so:
Test/Validation:
No comments:
Post a Comment