0
최대 힙 백업 세트에서 검색에 대한 최악의 시간 복잡도는 얼마입니까? 세트에서 가장 작은 항목을 찾으면 O (n) 시간이 걸릴 수 있습니다. 맞습니까? 더 빠른 방법이 있습니까?최대 힙 백업 세트 효율성 향상
A
답변
1
최대 힙에서 가장 작은 항목을 찾는 것은 O (n) 작업입니다. Min-max heap을 구현하면 O (log n) 삽입 및 제거를 유지하면서 최소 및 최대 항목에 O (1) 액세스 권한을 부여 할 수 있습니다. 그러나 전체적인 최소 최대 힙은 상수 요인으로 인해 최대 힙보다 조금 느립니다.
가장 큰 힙을 skip list으로 바꿀 수 있습니다. 그러면 가장 작은 항목에 O (log n) 액세스가 부여됩니다. 그러나 건너 뛰기 목록을 구현하는 것은 바이너리 힙을 구현하는 것보다 좀 더 복잡하며 더 많은 메모리를 소비 할 수 있습니다.