почему алгоритм кода Хаффмана с 2 очередями и отсортированным входом cna быть O (n)

Question

Я прочитал этот алгоритм для использования двух очередей для реализации кодов Хаффмана, и он утверждает, что с отсортированным вводом время выполнения может быть O (n): https://www.geeksforgeeks.org/efficient-huffman-coding-for-sorted-input-greedy-algo-4/

Я не вполне понятно, почему это O (n): алгоритм перебирает все начальные N узлов, однако он будет создавать объединенный узел и помещать его во вторую очередь во время итерации. Похоже, что на весь процесс итерации у меня уйдет O (n log n).

Answer 1

На каждом шаге вы выводите из очереди 2 узла (время O (1)), строите новый узел (время O (1)) и ставите в очередь 1 узел (время O (1)). Количество узлов в очереди начинается с n и уменьшается на единицу на каждом шаге, так что остается ровно n-1 шагов, прежде чем останется единственный узел. элементы не начинают сортироваться (по частоте), так как для инициализации алгоритма вы должны поставить элементы в первую очередь в порядке убывания частоты, поэтому вам нужно их отсортировать. Если они уже отсортированы, вы можете поставить их в очередь за O (n) раз.