Оглядываясь на мой тест для структур данных, я заметил что-то, когда перебирал его, может кто-то помочь и ответить, какова средняя временная стоимость (большой O) поиска макс. ключ в мини-куче (очередь приоритетов), будет ли это O (log N) или это O (N)?Какова средняя временная стоимость min heap
Поиск максимального элемента в минимальной куче O(N).
Вам нужно будет перейти на самый нижний уровень в дереве (до половины детей) и проверить каждый из них, поскольку они не имеют особого порядка относительно друг друга.
Это потребует проверки около N/2 узлов, которые (при условии, что вы используете стандартный алгоритм для нахождения максимума): O(N).
Если вы заинтересованы в поиске максимального элемента в куче, вы можете использовать максимальную кучу. Если память не вызывает большого беспокойства, вы можете использовать как максимальную кучу, так и минимальную кучу, которая позволит вам получить O(1) для получения максимального и минимального элементов.
Полезная страница: http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o – hexparrot