배열에서 K번째로 큰 요소 찾기

선택, 힙 찾기, 빠른 정렬이라는 세 가지 주요 솔루션이 있는 매우 중요한 질문입니다.

더 나은 방법은 힙 정렬과 빠른 정렬입니다. 빠른 정렬은 이미 분석했으므로 여기서는 힙 정렬이 어떻게 문제를 해결하는지 살펴보겠습니다.

이 문제는 큰 힙과 작은 힙으로 해결할 수 있지만, 가장 큰 힙을 찾을 때는 작은 힙을, 가장 작은 힙을 찾을 때는 큰 힙을, 중간을 찾을 때는 두 개의 힙을 사용하는 것이 더 이해하기 쉽고 적용 범위도 넓어지므로 권장합니다. 상황을 더 잘 설명하기 위해 [3,2,3,1, 2 ,4 ,5, 1,5,6,2,3] 수열을 확장하여 크기 4의 작은 루트 더미를 구성합니다.

힙이 가득 차면 작은 루트 힙의 경우 모든 새 요소가 반드시 힙에 들어갈 수 있는 것은 아니며, 루트 요소보다 큰 요소만 힙에 삽입할 수 있고 그렇지 않으면 그냥 버려집니다. 이것은 매우 중요한 전제입니다.

또한 요소가 들어올 때 루트 요소가 먼저 교체되는데, 왼쪽과 오른쪽 하위 트리가 모두 작다면 어떻게 해야 할까요? 당연히 루트 요소가 현재 힙에서 가장 작아야 하므로 더 작은 요소와 비교해야 합니다. 두 자식의 값이 같다면 어떨까요? 그런 다음 무작위로 하나를 선택합니다.

새 요소는 단순히 루트 요소를 교체한 다음 작은 힙으로 재구성하는 방식으로 삽입되며, 완료되면 마술처럼 이 시점에서 루트의 루트 요소가 4번째로 큰 요소가 되는 것을 발견할 수 있습니다.

이 시점에서 처리할 시퀀스의 크기나 고정 여부에 관계없이 루트 요소는 매번 현재 시퀀스에서 정확히 K 번째로 큰 요소라는 것을 알 수 있습니다. 위의 그림은 공간의 제약을 고려하여 링크의 조정 부분을 생략한 것으로, 독자들이 직접 확인하실 수 있도록 그려보시기 바랍니다.

달성하기 위해 자체적으로 코드는 매우 어렵고 JDK 우선 순위 대기열을 사용하여 문제를 해결할 수 있으며 아이디어는 매우 간단합니다. 실제로 가장 큰 K 요소를 찾는 것은 가장 작은 요소의 후반부 이후에 정렬 된 전체 배열입니다. 따라서 K 요소의 최소 힙을 유지할 수 있습니다:

• 현재 힙이 가득 차 있지 않으면 직접 추가하세요;
• 힙이 가득 찼을 때 새로 읽은 숫자가 힙의 최상위보다 작거나 같으면 찾을 요소가 아니어야 하며, 새로 탐색한 숫자가 힙의 최상위보다 크면 힙의 최상위를 꺼내서 새로 읽은 숫자를 넣어 힙이 스스로 내부 구조를 조정할 수 있도록 합니다.

참고: 여기서 가장 적절한 연산은 실제로 새로 읽은 요소를 힙의 맨 위에 배치한 다음 싱크 연산을 수행하는 replace()입니다. Java의 PriorityQueue는 이 연산을 제공하지 않으므로 poll()과 offer()를 사용해야 합니다. 우선순위 큐는 다양한 방식으로 작성되며, 여기서는 대표적인 예시일 뿐 다른 작성 방식도 동일하며 본질적인 차이는 없습니다.

public int findKthLargest(int[] nums, int k) {
 if (k > nums.length) {
 return -1;
 }
 int len = nums.length;
 // k개의 요소로 최소 힙 사용
 PriorityQueue<Integer> minHeap = new PriorityQueue<>(k,(a,b) -> a - b);
 for (int i = 0; i < k; i++) {
 minHeap.add(nums[i]);
 }
 for (int i = k; i < len; i++) {
 // 링크된 목록의 수를 감안할 때 힙이 정의된 크기는 어느 정도일까요?
 Integer topEle = minHeap.peek();
 // 현재 트래버스된 요소가 힙의 최상위 요소보다 크면 힙의 최상위가 튀어나오고 트래버스된 요소가 들어갑니다.
 if (nums[i] > topEle) {
 minHeap.poll();
 minHeap.offer(nums[i]);
 }
 }
 return minHeap.peek();
}

힙 정렬의 원리

찾기: 작은 것을 찾아서 크게 사용, 큰 것을 찾아서 작게 사용

정렬: 오름차순에는 작게, 내림차순에는 크게 사용합니다.

이전에 힙을 사용하여 특별한 경우를 찾는 방법을 소개했는데, 힙의 또 다른 매우 중요한 역할은 정렬 할 수 있으며 정렬하는 방법은 무엇입니까? 사실, 매우 간단하고 힙의 큰 상단에서 루트 노드가 전체 구조의 가장 큰 요소라는 것을 알고 먼저 제거하고 나머지 재 배열은 현재 루트 노드가 두 번째로 큰 요소이며 다시 제거한 다음 행을 제거합니다. 마지막으로 힙에 요소가 하나만 남았을 때 제거된 데이터도 올바른 순서로 정렬되어 있지 않나요?

구체적으로, 힙 구축이 끝나면 배열의 데이터는 이미 빅 탑 힙의 특성에 따라 정리되어 있습니다. 배열의 첫 번째 요소는 힙의 맨 위에 있는 가장 큰 요소입니다. 마지막 요소와 바꾸면 가장 큰 요소는 아래 첨자 n이 있는 위치로 이동합니다.

이 과정은 "힙의 최상위 요소 제거" 작업과 다소 유사한데, 힙의 최상위 요소를 제거하면 첨자가 n인 요소를 힙의 맨 위에 놓고 나머지 n-1 요소는 힙핑의 방법으로 힙으로 재구성합니다. 힙이 완성되면 힙의 맨 위에 있는 요소를 가져와서 첨자가 n-1인 위치에 놓고, 이 과정을 반복하여 힙에 1이라고 표시된 요소가 하나만 남으면 정렬이 완료됩니다.

물론 위의 과정에서 마지막 위치에 배치된 요소는 정렬 및 계산에 관여하지 않습니다.

위의 [12 23 54 2 65 45 92 47 204 31] 시퀀스를 정렬하는 예제를 보면 먼저 빅 탑 힙을 구성한 다음 매번 루트 요소를 힙에서 빼내고 나머지는 빅 탑 힙으로 계속 조정하는 방식입니다:

이 시점에서 더미의 순서가 204, 92, 65, 54, 47, 45....임을 알 수 있습니다. 즉, 순서는 큰 것부터 작은 것까지입니다. 따라서 작은 상단 더미인 경우 자연스럽게 오름차순이라는 것을 이해할 수 있습니다. 따라서 정렬할 때

정렬: 오름차순에는 작게, 내림차순에는 크게 사용합니다.

이는 이전 조회와 반대입니다.

이러한 더미의 특성을 이해하면 관련 주제를 스트레스 없이 수행할 수 있습니다.

이 문제에 접근하는 대여섯 가지 방법을 살펴봤다면, 이제 힙 정렬이 어떻게 이 문제를 해결하는지 알아보겠습니다. 각 큐는 가장 작은 것부터 가장 큰 것 순으로 정렬되므로 매번 가장 작은 요소를 찾기 때문에 작은 루트 힙이 사용되며, 똑같은 방식으로 구성되고 큰 최상위 힙과 동일하게 작동하지만 매번 누가 더 작은지 비교한다는 차이점이 있습니다. 힙 병합을 사용하는 전략은 연결된 목록이 아무리 많아도 모두 순서대로 끝나는 것입니다. 매번 나머지 노드 중 가장 작은 값을 출력 체인 테이블의 끝에 추가한 다음 힙을 조정하고, 최종적으로 힙이 비워지면 병합이 완료됩니다.

이 힙은 얼마나 크게 정의해야 할까요? 힙은 주어진 연결된 테이블의 수만큼 크도록 정의됩니다.

public ListNode mergeKLists(ListNode[] lists) {
 if (lists == null || lists.length == 0) return null;
 
 PriorityQueue<ListNode> q = new PriorityQueue<>(Comparator.comparing(node -> node.val));
 for (int i = 0; i < lists.length; i++) {
 if (lists[i] != null) {
 q.add(lists[i]);
 }
 }
 
 ListNode dummy = new ListNode(0);
 ListNode tail = dummy;
 
 while (!q.isEmpty()) {
 tail.next = q.poll();
 tail = tail.next;
 if (tail.next != null) {
 q.add(tail.next);
 }
 }
 return dummy.next;
}