O (1) 시간에 최대 힙의 10 번째로 큰 요소 찾기

Question

O (1)에서 n 개의 고유 한 요소로 최대 힙의 10 번째 큰 요소를 찾는 알고리즘을 구현하려고합니다.) 시각.

힙 속성을 사용하여 그려 보려고했지만 힙이 더 깊어지면서 점점 더 복잡해졌습니다. 이것은 내가 작성한 초안이며 내가 붙어있는 곳입니다. - 우리가 별개의 요소와 힙 속성을 가지고 있기 때문에 부모는 항상 그 자식보다 큽니다. 따라서 루트는 최대 요소입니다. 다음 최대 요소는 루트의 자식 사이의 더 큰 요소입니다.

편집 : 나는 또한 더 큰 하나의 아들과 다른 하나의 부모를 비교하는 것에 대해서 생각했습니다. 그들 중 적어도 하나가 다른 부모보다 더 큰 경우, 힙 속성에 의해 우리는 최대 아들로부터 계속해서 우리가 10 가지 요소를 가질 때까지 계속하지만, 더 깊어지면서 요소가 없어지므로 항상 그렇지 않습니다. 다시 모든 곳으로 돌아갈 필요가 있습니다.

모든 설명이나 의사 코드가 훨씬 유용 할 것입니다.

미리 감사드립니다.

Answer 1

가능한 가장 쉬운 해결책은 금식이 아니지만 여전히 O (1)은 힙의 모든 최상위 요소 (트리로 표시)를 레벨 10까지 추출하는 것입니다. 그런 다음 정렬하여 열 번째 요소.

O (1) 노력으로 이어지는 추출 된 요소의 수가 제한된다는 점에 유의하십시오.