Как отслеживать узлы в дереве, используя хеш-таблицу?

Question

Я пытаюсь реализовать кучу Фибоначчи, и мне необходимо отслеживать ее узлы для последующих операций. Для непосвященных куча Фибоначчи может рассматриваться как дерево m-степени или набор деревьев с указателем на максимальный узел в структуре. Древовидная структура принимает слово и его частоту в качестве входных данных и должна давать наиболее часто встречающиеся слова в качестве выходных данных. Например, ввод:

Ann 31
Dustin 27
Ryan 43
Ashley 13
Sunday 23
Tuesday 19
2 //Output two top most occurring words in the tree

Output:
Ryan, Ann

Мое понимание хеш-таблицы очень элементарно. Я ввожу слово в качестве ключа, и оно выдает хеш-значение в качестве вывода. Как заставить этот вывод быть указателем на соответствующий узел в дереве, в котором хранится его частота? Кроме того, учитывая входные данные, чтобы найти 'n' часто встречающихся слов, могу ли я повторно удалить верхний узел 'n' раз и снова вставить его обратно в структуру? Или мне лучше хранить отсортированный хэш-стол?

Answer 1

Как кто-то, кто закодировал один из них раньше, есть несколько разных способов сделать то, что вы пытаетесь сделать.

1. Пусть функция вставки возвращает указатель на узел внутри структуры, а затем использует некоторую вспомогательную хэш-таблицу для хранения этих указателей. Чтобы выполнить вставку, вы должны вставить ключ и его приоритет, получить указатель на узел в куче Фибоначчи, а затем добавить ключ и указатель на внешнюю хеш-таблицу (в Java что-то вроде HashMap; в C++ что-то вроде std::unordered_map; Я бы посоветовал не кататься самостоятельно).

2. Используйте навязчивую структуру данных, чтобы каждый ключ для хранения в куче Фибоначчи фактически являлся полной структурой узла. Реализация кучи Фибоначчи тогда перезапишет соответствующие поля ввода, чтобы связать ее со структурой кучи, и при условии, что вы сохранили узлы некоторым разумным способом, вы можете просто искать их по мере необходимости.

Я лично считаю, что опция (1) является более чистой, чем опция (2) для большинства приложений, но есть причины предпочесть (2), а не (1).

В мета-заметке, кучи Фибоначчи общеизвестно трудны для кодирования и на практике значительно медленнее, чем двоичные кучи, даже несмотря на то, что они асимптотически быстрее в ряде случаев использования. Я бы посоветовал не использовать его на самом деле, если только у вас нет веских причин для этого.