해시 테이블을 사용하여 트리의 노드를 어떻게 추적합니까?

Question

피보나치 힙을 구현하려고하는데 이후 작업을 위해 노드를 추적해야합니다. 초기화되지 않은 피보나치 힙은 m-degree 트리 또는 구조의 최대 노드에 대한 포인터가있는 트리 모음으로 간주 될 수 있습니다. 트리 구조는 단어 및 해당 빈도를 입력으로 사용하며 자주 발생하는 단어를 출력으로 제공해야합니다. 예를 들어 , 입력 : 해시 테이블의

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).

메타 노트에서 피보나치 힙은 많은 유스 케이스에서 점근적으로 빠르더라도 코드 작성이 어렵고 실제로는 바이너리 힙보다 훨씬 느리기 때문에 악명이 높습니다. 설득력있는 이유가 없다면 실제로 사용하지 말라고 조언합니다.