Очередь с приоритетами, скорость работы?

Question

[redfoo]

Здравствуйте, написал алгоритм, реализующий очереди с приоритетами на базе max-heap, с функцией вставки и извлечения максимального элемента, по моим измерениями время работы не выходит за O(logn), но, видимо, я в чем то ошибаюсь, так как stepik не принимает решение с ошибкой Time limit exceeded, подскажите, в чем ошибка.

from sys import stdin
from _heapq import _heappop_max
from _heapq import _heapify_max

class PriorityQueue:
	def __init__(self):
		self.queue = []
	
	def Insert(self, p):
		self.queue.append(p)
		_heapify_max(self.queue)

	def GetMax(self):
		return _heappop_max(self.queue)

def main():
	queues = PriorityQueue()
	reader = (tuple(line.split()) for line in stdin)
	n = next(reader)
	data = list(reader)
	for key in data:
		if key[0] == 'Insert':
			queues.Insert(int(key[1]))
		elif key[0] == 'ExtractMax':
			print(queues.GetMax())

if __name__ == '__main__':
	main()

Answer 1

[longclaps]

Вы меня извините, при всём уважении, вы - говнокодер. С этим надо что-то делать, для начала - признать этот факт. Возьмём самую длинную строку:

reader = (tuple(map(str, line.split())) for line in stdin)

чем она отличается от
reader = (tuple(line.split()) for line in stdin)
Ответ - вызовом map, который бессмысленно переводит str в str. Вы зачем это сделали? Там в задании (я не поленился, погуглил) был шаблон решения с рабочим проверочным кодом, а вы зачем-то заменили его странным не буду повторять чем.

По существу: сложность алгоритма оценивается не измерениями, а мозгами. _heapify_max, комментарии в исходниках:

""" Maxheap variant of heapify. """

Смотрим heapify:

""" Transform list into a heap, in-place, in O(len(heap)) time. """

И где тут O(logn)?

Попробуйте придумать нормальное решение.

Comments

[redfoo]

Спасибо, вот я и пытаюсь что то сделать с этим, к сожалению, это не так то просто.