#priority-queue
#приоритетная очередь
Вопрос:
Я написал программу для вычисления медианы текущей последовательности с использованием двух очередей приоритета min и max. Сравнивая входные данные с текущей медианой, они помещаются в очередь в зависимости от его значения. Путем сравнения размеров очереди определяется медианный can.
Я должен выдвинуть гипотезу и проверить время выполнения программы. Из тестирования и построения графика для разных входных размеров я вижу, что время выполнения действительно линейно.
Это меня удивляет, причина в том, что я думал, что чем больше очередей, тем больше времени требуется для размещения правильного значения в корне? или размер очереди не имеет отношения к размещению правильного значения в корне (как кажется в моих результатах).
Если бы кто-нибудь мог уточнить стоимость приоритетной очереди, это было бы очень здорово.
Комментарии:
1. Можете ли вы описать свой алгоритм более подробно? Например, как вы «ставите в очередь в зависимости от ее значения»? И как вы определяете медиану на основе размеров очереди?
2. Я сравниваю входные данные с текущей медианой и помещаю их в очередь max, если < медиана и минимальная очередь, если> медиана. Если очереди имеют одинаковый размер, медиану изменять не нужно. Если единица больше более чем на 1, то корень заменяется на другую очередь, и новая медиана является либо корнем одной из очередей (верхняя или нижняя медиана), либо средним значением корней. Это еще не все, но это основа всего.
3. Как вы сказали «root», я полагаю, вы используете реализацию приоритетной очереди с максимальной и минимальной кучами? Это имеет стоимость
O(log n)4. Да, вы совершенно правы. Я еще раз взглянул на свои данные, и с моей стороны у меня был пробел, результаты показывают, что O (log n) стоит отлично. Большое вам спасибо