Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
A class to calculate the median of a leading sliding window at the back of a stream of integer values. More...
Public Member Functions | |
WindowedMedian (size_type windowSize) | |
Constructs a WindowedMedian object. | |
void | insert (int value) |
Insert a new value to the stream. | |
float | getMedian () const |
Gets the median of the values in the sliding window. | |
float | getMedianNaive () const |
A naive and inefficient method to obtain the median of the sliding window. Used for testing! | |
Private Member Functions | |
void | insertToSorted (int value) |
Inserts a value to a sorted multi-value BST. | |
void | eraseFromSorted (int value) |
Erases a value from a sorted multi-value BST. | |
Private Attributes | |
const size_type | _windowSize |
sliding window size | |
Window | _window |
a sliding window of values along the stream | |
std::multiset< int > | _sortedValues |
std::multiset< int >::const_iterator | _itMedian |
A class to calculate the median of a leading sliding window at the back of a stream of integer values.
|
inlineexplicit |
Constructs a WindowedMedian object.
windowSize | Sliding window size |
|
inlineprivate |
Erases a value from a sorted multi-value BST.
value | Value to insert |
If the erased value is on the left branch or the median itself and the number of elements is even, the new median will be the right child of the current one
O(1) - traversing one step to the right child
However, if the erased value is on the right branch or the median itself, and the number of elements is odd, the new median will be the left child of the current one
Find the (first) position of the value we want to erase, and erase it
|
inline |
Gets the median of the values in the sliding window.
O(1)
|
inline |
A naive and inefficient method to obtain the median of the sliding window. Used for testing!
Sort window - O(NlogN)
Find value in the middle - O(N)
O(N)
|
inline |
Insert a new value to the stream.
value | New value to insert |
Push new value to the back of the sliding window - O(1)
If exceeding size of window, pop from its left side
Erase from the multi-value BST the window left side value
Pop the left side value from the window - O(1)
|
inlineprivate |
Inserts a value to a sorted multi-value BST.
value | Value to insert |
Insert value to BST - O(logN)
For the first value, set median iterator to BST root
If new value goes to left tree branch, and number of elements is even, the new median in the balanced tree is the left child of the median before the insertion
However, if the new value goes to the right branch, the previous median's right child is the new median in the balanced tree
O(1) - traversing one step to the right child
|
private |
an iterator that points to the root of the multi-value BST
|
private |
a DS to represent a balanced multi-value binary search tree (BST)