Онлайн курс продолжает не нравиться
Как уже говорил, в введении нет основ, при этом в дальнейшем лектор вовсю оперирует терминами вроде "инвариант цикла".
Построение материала по сложности тоже некорректное. Сначала код Хаффмана, затем очередь с приоритетами. Хотя в реализации первого требуется второе.
Ну и тесты.
Отсутствие входных данный, на которых ломается алгоритм, преподаватели объяснили тем, что иначе задача решается перебором. Я правда неопытный программист, и потому не понимаю, как можно алгоритм написать путем перебора входных данных.
Наличие тестов времени вызывает вопрос: этот курс точно рассчитан на неподготовленного читателя?
Вот как раз тема с очередью. Нужно вставлять числа и извлекать максимальное. Ограничений на реализацию нет.
Написал вариант через двусвязный список, поскольку со списком я худо-бедно умею работать.
Не проходит тест времени. Ок, понятно. Много времени уходит на вставку в конец и поиск максимума.
Переписал со вставкой максимума в корень, извлекается теперь всегда первый.
Снова не проходит тест времени.
А вот тут хз.
Извлечение - константное время (поменять местами несколько указателей).
Вставка - мне тяжело оценить, но должна совпадать с первым вариантом только при сортировке по убыванию, в остальных лучше.
Буду пробовать через кучу, только сначала найду нормальное описание этой структуры. Там вставка вроде log(N).
И нет, я не жалуюсь.