Возможный дубликат:
Передвижной медианный алгоритм в C
Учитывая, что целые числа считываются из потока данных. Найти медианную часть элементов, прочитанных до сих пор эффективным способом.
Решение, которое я прочитал: мы можем использовать максимальную кучу на левой стороне, чтобы представлять элементы, которые меньше эффективной медианной, и минимальную кучу с правой стороны, чтобы представлять элементы, которые больше эффективной медианной.
После обработки входящего элемента количество элементов в кучах отличается не более чем на 1 элемент. Когда обе кучи содержат одинаковое количество элементов, мы находим среднее значение данных корня кучи как эффективную медианную. Когда кучи не сбалансированы, мы выбираем эффективную медиану из корня кучи, содержащей больше элементов.
Но как бы мы построили максимальную кучу и минимальную кучу, то есть как мы узнаем эффективную медиану здесь? Я думаю, что мы вставим 1 элемент в max-heap, а затем следующий 1 элемент в min-heap и т.д. Для всех элементов. Исправьте меня, если я ошибаюсь.