배열을 사용하지 않고 힙 구현

Question

Google 개발자 인터뷰를 위해 준비 중이며 힙에 대한 질문이 없습니다. 동적 이진 트리 (배열이 아님)로 힙을 구현해야합니다. 각 노드에는 부모 노드와 두 자식 노드에 대한 포인터가 있으며 루트 노드에 대한 전역 포인터가 있습니다. 이 책은 "왜 이것이 충분하지 않을까요?"라고 묻습니다.

표준 트리 구현이 힙 작업을 추가를 지원하도록 확장 할 수있는 방법을() 및 deleteMin()? 이 데이터 구조에서 이러한 작업을 어떻게 구현할 수 있습니까?

Answer 1

전체 노드의 크기를 유지할 수 있습니까? 그렇다면 새로운 요소를 어디에 추가해야하는지 쉽게 알 수 있습니다. 왜냐하면 그것이 거의 완전한 나무이기 때문입니다.

deleteMin에 대해서는 array (N/2)처럼 모든 잎에 직접 액세스 할 수 없기 때문에 효과가 떨어질 것으로 생각합니다. 잎이 생길 때까지 모든 경로를 거쳐야합니다. O (n)