Является ли FibonacciHeap мини-кучей? Как найти Макс, используя FibonacciHeap?
Мой Java-проект состоит в том, чтобы использовать кучу Макса Фибоначчи для поиска самых популярных хэштегов. Запись может быть такой:
#saturday 5
#sunday 3
#saturday 10
#monday 2
#reading 4
#playing_games 2
3
Но в куче Фибоначчи есть только функция поиска мин. В чем разница между "кучей Фибоначчи", "минимальной кучей Фибоначчи" и "максимальной кучей Фибоначчи"?
Моя идея состоит в том, чтобы использовать функцию extractmax() n раз, чтобы получить верхнюю часть n. но я не знаю, что такое куча Макса Фибоначчи.
2 ответа
Переключение между минимальной и максимальной кучей тривиально, вы просто меняете компаратор. Куча - это куча, в каком бы направлении она ни работала, алгоритм не меняется.
Найти максимальный элемент - это просто найти минимальный элемент, за исключением того, что вы изменили порядок.
Вместо использования минимальных куч в структуре, используйте максимальные кучи.