Как реализовать автозаполнение с помощью алгоритма лучших предложений?
Это вопрос для интервью: напишите программу для реализации автозаполнения для заданного набора из N строк и положительных весов. То есть, учитывая префикс и целое число k, найдите верхние k строк в наборе среди тех, которые начинаются с префикса.
И здесь я нашел предложенный алгоритм с троичным деревом поиска и максимальной кучей: http://www.cs.princeton.edu/courses/archive/fall13/cos226/checklist/autocomplete.html
Я вроде получаю алгоритм, но не знаю, как распечатать лучшие слова. У меня есть одна большая путаница: мы можем пройти по дереву и получить все узлы с максимальными весами, но как нам вернуться назад и собрать слова вместе?
Любая помощь приветствуется.