다음과 같이 전 질문 시험이 시간 O (K) 공간

Question

(K 로그) O으로 세트 S로부터 K 위의 int 저장. 처음에는 S가 비어 있습니다. 그런 다음 새 정수 이 하나씩 추가되지만 결코 삭제되지 않습니다. k를 고정 된 정수라고하자.

알고리즘을 에 S로 k 최대 정수를 유지하도록 지정하십시오. 알고리즘은 항상 0 (k) 공간을 사용해야합니다. 크기 | S | (S |가 계속 증가하지만 공간은 없습니다).

또한, O (log k) 시간에 모든 정수 삽입을 처리해야합니다.

예를 들어,이 K = 3을 가정하고, 삽입 된 정수의 시퀀스가 ​​있음을 83, 21, 66, 5, 24, 76, 92, 32, 43 ... 알고리즘 (83) {유지되어야 76 삽입 후 {83, 66, 76} , 삽입 후 {83, 76, 92} 삽입 후 43, 128, 나는 이것을 어떻게 완성 할 수 있을까 ??

Answer 1

크기 힙의 최소 힙을 사용하여 해결할 수 있습니다. 최소 힙은 각 내부 노드의 값이 해당 노드의 하위 값보다 작거나 같은 완전한 2 진 트리입니다. 하지만 힙의 크기를 제한하고 새로운 요소를 얻을 때마다 힙에 이미있는 다른 요소를 확인하지 않으면 해당 요소가 루트 요소보다 큰지 확인하십시오. 새로운 요소를 가진 그 요소. 당신이 요구했듯이 그것은 O (k) 공간을 필요로하고 삽입 시간 또한 O (log k)입니다. 희망이 당신을 돕는다.