힙을 사용하여 O (1) 공간에서 k-messed-array 정렬을 수행 할 수 있습니까?

Question

배열의 모든 요소가 왼쪽에서 오른쪽으로 올바른 위치에서 최대 k 위치 떨어져있는 익숙한 문제에서, 최소 힙 구현은 다음과 같습니다.

크기 k + 1의 최소 힙을 생성하십시오. 따라서 min 힙의 루트는 정렬 된 배열의 가장 작은 요소 인 입니다. 나머지 n (k + 1) 요소의 경우 각 반복에서 이미 힙에있는 요소 [i]와 사이에 선택됩니다. 따라서 힙에 [i]를 넣고 heapify하고 min을 추출하십시오. 이렇게하면 정렬 된 배열의 요소 인 [i-k] 이 계속 채워집니다.

시간 복잡도 : O (K) + O (NK) .LOG (K)

공간 복잡도 : O (K)

내 질문이있다

이이 O를 사용하여 수행 할 수 있습니다 (1) 공간 복잡성?

접근 방식은 here이지만 발견 할 수는 없습니다. 누군가가 정교 할 수 있을까요?

이 작업을 수행 할 수 있습니다. 맨 끝에서 시작하여 최소 힙 대신 최대 힙 을 사용하십시오. 그 2K 요소의 마지막 블록 을 적절히 확장하십시오. 추출 된 첫 번째 요소를 변수에 저장합니다. 후속 요소는 heapsort와 비슷한 2k (힙 구조 포함) 블록의 최종 블록 바로 앞의 비워진 위치로 이동합니다. 단지 1 블록 만 남았을 때, 그것을 제자리에 둡니다. 최종 최종 블록을 초기 블록 블록으로 "회전"하려면 O (n) 패스가 필요합니다. 회전은 간단하지 않지만 O (n) 및 O (1) 공간에서 수행 할 수 있습니다.

Answer 1

기본적인 개념은 배열에 힙을 저장하고, 배열의 나머지 요소를 정렬 한 다음 힙 부분 자체를 정렬하는 것입니다.

여기에는 이해하기 쉬운 최소 힙 (heap)을 사용하는 변형이 있습니다.

1. 배열의 첫 번째 k+1 요소를 무력화합니다. 힙의 최소 요소는 전체 배열의 최소값입니다.

   k+1 | n-(k+1) 
   heap | unsorted 
   

2. 스왑 정렬되지 않은 부분과 재 heapify의 첫번째 요소 힙의 최소 요소.

   k+1 | 1  | n-(k+2) 
   heap | sorted | unsorted 
   

3. 처리되지 않은 요소가 없어 질 때까지 2 단계를 반복하십시오. 이 시점에서 힙은 k+1 배열의 가장 큰 요소를 포함하고 나머지 요소는 정렬 된 순서로 있습니다.

   k+1 | n-(k+1) 
   heap | sorted 
   

4. 정렬 배열

   k+1   | n-(k+1) 
   sorted heap | sorted 
   

5. 이동 어레이의 반대쪽 정렬 힙 힙 부.이제 배열이 정렬됩니다.

   n-(k+1)| k+1 
   sorted | sorted heap