Możliwy duplikat:
Rolujący algorytm mediany w C

Biorąc pod uwagę, że liczby całkowite są odczytywane ze strumienia danych. Znajdź medianę dotychczas przeczytanych elementów w efektywny sposób.

Rozwiązanie Przeczytałem: Możemy użyć sterty maksymalnej po lewej stronie, aby reprezentować elementy, które są mniejsze niż efektywna mediana, i sterty min po prawej stronie, aby reprezentować elementy, które są większe niż skuteczna mediana.

Po przetworzeniu przychodzącego elementu liczba elementów w stosach różni się co najwyżej o 1 element. Gdy oba stosy zawierają taką samą liczbę elementów, średnia danych źródłowych sterty jest skuteczną medianą. Gdy hałdy nie są zrównoważone, wybieramy efektywną medianę z korzenia sterty zawierającej więcej elementów.

Ale w jaki sposób skonstruowalibyśmy maksymalną stertę i stertę min, czyli jak znalibyśmy tutaj efektywną medianę? Myślę, że wstawilibyśmy 1 element do max-sterty, a następnie następny 1 element do sterty min i tak dalej do wszystkich elementów. Popraw mnie, jeśli się mylę.