Java 데이터 구조의 최소 힙과 최대 힙의 원리와 구현에 대한 자세한 설명
이 기사에서는 java에 대한 관련 지식을 제공합니다. 컴퓨터 과학에서 힙의 구현은 배열에 트리 구조를 구축하고 힙의 속성을 충족할 수 있는 트리 기반의 특수한 데이터 구조입니다. Java 데이터 구조의 힙에 대해 자세히 알아볼 수 있습니다.
추천 학습: "java 비디오 튜토리얼"
1. 소개
힙의 역사
힙의 데이터 구조에는 2-3 힙, B 힙, 피보나치 바이너리 등 다양한 형태가 있습니다. Java API에서 가장 일반적으로 사용되는 바이너리 힙은 우선 순위 큐를 구현하는 데 사용되는 바이너리 힙으로 1964년 JWJ Williams가 힙 정렬 알고리즘을 위한 데이터 구조로 도입했습니다. 또한 Dijkstra 알고리즘과 같은 여러 효율적인 그래프 알고리즘에서도 힙은 매우 중요합니다.
2. 힙 데이터 구조
컴퓨터 과학에서 힙의 구현은 트리 기반의 특수한 데이터 구조로, 배열에 트리 구조를 구축하고 힙의 속성을 충족할 수 있습니다.
최소 힙: P가 C의 상위 노드인 경우 P의 키(또는 값)는 C의 해당 값보다 작거나 같아야 합니다.
최대 힙: 최소 힙 정의와 정반대입니다. 최대 힙(최대 힙)에서는 P의 키(또는 값)가 C의 해당 값보다 큽니다.
3. 힙 코드 구현
1. 구현 소개
Java API의 힙 구현은 주로 지연 대기열 바이너리 힙 구현에 반영됩니다. 여기서 Fu 형제는 코드의 이 부분을 분할합니다. 별도로 작은 힙과 큰 힙의 구현에 대해 알아보세요.
힙의 데이터 구조 소개부터 작은 힙과 큰 힙의 유일한 차이점은 요소를 정렬하는 방식임을 알 수 있습니다. 즉, 요소를 저장하고 검색할 때와 요소를 채우고 제거할 때 정렬 방법이 다릅니다.
2. 힙 구현
힙에 요소를 저장할 때 해당 특성을 따르기 위해 저장 프로세스 중에 대기열 끝에 있는 요소를 비교하여 위로 이동합니다.
private void siftUpComparable(int k, E x) { logger.info("【入队】元素:{} 当前队列:{}", JSON.toJSONString(x), JSON.toJSONString(queue)); while (k > 0) { // 获取父节点Idx,相当于除以2 int parent = (k - 1) >>> 1; logger.info("【入队】寻找当前节点的父节点位置。k:{} parent:{}", k, parent); Object e = queue[parent]; // 如果当前位置元素,大于父节点元素,则退出循环 if (compareTo(x, (E) e) >= 0) { logger.info("【入队】值比对,父节点:{} 目标节点:{}", JSON.toJSONString(e), JSON.toJSONString(x)); break; } // 相反父节点位置大于当前位置元素,则进行替换 logger.info("【入队】替换过程,父子节点位置替换,继续循环。父节点值:{} 存放到位置:{}", JSON.toJSONString(e), k); queue[k] = e; k = parent; } queue[k] = x; logger.info("【入队】完成 Idx:{} Val:{} \r\n当前队列:{} \r\n", k, JSON.toJSONString(x), JSON.toJSONString(queue)); }
힙에 add 메소드를 추가하는 구현은 결국 정렬 방식으로 처리하기 위해 siftUpComparable 메소드를 호출하게 됩니다. 이 정렬 CompareTo 메서드는 특정 MinHeap 및 MaxHeap에 의해 구현됩니다.
그림에 표시된 대로 힙 요소 2를 예로 들어 보겠습니다.
먼저 요소 2를 대기열 끝에 걸어 놓은 다음 (k - 1)>>> 1을 통해 상위 노드의 위치를 계산하고 해당 요소와의 교환을 비교하고 판단합니다.
교환 과정에는 2->6, 2->5가 포함되며 그 이후에는 요소가 저장됩니다.
3. 힙에서
요소를 구현하는 것은 실제로 매우 간단합니다. 루트 요소를 삭제하고 직접 팝업하면 됩니다. 그러나 루트 요소가 마이그레이션된 후 반대편으로 마이그레이션하려면 또 다른 최소 요소를 찾아야 하기 때문에 나머지 단계는 복잡합니다. 이 프로세스는 힙에 들어가는 것과 정확히 반대되는 지속적인 하향 마이그레이션 프로세스입니다.
private void siftDownComparable(int k, E x) { // 先找出中间件节点 int half = size >>> 1; while (k < half) { // 找到左子节点和右子节点,两个节点进行比较,找出最大的值 int child = (k << 1) + 1; Object c = queue[child]; int right = child + 1; // 左子节点与右子节点比较,取最小的节点 if (right < size && compareTo((E) c, (E) queue[right]) > 0) { logger.info("【出队】左右子节点比对,获取最小值。left:{} right:{}", JSON.toJSONString(c), JSON.toJSONString(queue[right])); c = queue[child = right]; } // 目标值与c比较,当目标值小于c值,退出循环。说明此时目标值所在位置适合,迁移完成。 if (compareTo(x, (E) c) <= 0) { break; } // 目标值小于c值,位置替换,继续比较 logger.info("【出队】替换过程,节点的值比对。上节点:{} 下节点:{} 位置替换", JSON.toJSONString(queue[k]), JSON.toJSONString(c)); queue[k] = c; k = child; } // 把目标值放到对应位置 logger.info("【出队】替换结果,最终更换位置。Idx:{} Val:{}", k, JSON.toJSONString(x)); queue[k] = x; }
지속적으로 요소를 아래쪽으로 마이그레이션하세요. 이 프로세스는 왼쪽 및 오른쪽 자식 노드의 값을 비교하여 가장 작은 노드를 찾습니다. 그래서 전체 과정이 더미에 들어가는 것보다 더 번거로울 것입니다.
여기에서는 팝업 요소 1을 예로 들어 힙 끝에 있는 요소를 해당 위치로 바꿉니다. 전체 과정은 6개의 그림으로 나누어져 있습니다.
- 그림 1~그림 2에서 팝업할 루트 요소를 찾습니다.
- 그림 3에서 그림 4까지 루트 요소를 아래쪽으로 이동하고 하위 요소와 비교한 후 위치를 바꿉니다. 이 위치를 8과 비교하여 8보다 작으면 계속 하향 이동하게 됩니다.
- 그림 4부터 그림 5까지 마이그레이션을 계속하면 원래 노드 4의 위치에 해당하는 두 하위 요소가 모두 8보다 큽니다. 이때는 중지할 수 있습니다.
- 그림 5 ~ 그림 6, 요소 위치를 변경하고 대기열 끝에 있는 요소를 요소 1의 하향 이동 감지에 해당하는 위치로 교체합니다.
4. 작은 힙 구현
작은 힙은 양의 시퀀스 비교입니다
public class MinHeap extends Heap<Integer> { @Override public int compareTo(Integer firstElement, Integer secondElement) { return firstElement.compareTo(secondElement); } }
Test
@Test public void test_min_heap() { MinHeap heap = new MinHeap(); // 存入元素 heap.add(1); heap.add(3); heap.add(5); heap.add(11); heap.add(4); heap.add(6); heap.add(7); heap.add(12); heap.add(15); heap.add(10); heap.add(9); heap.add(8); // 弹出元素 while (heap.peek() != null){ logger.info("测试结果:{}", heap.poll()); } }
Result
17:21:30.053 [main] INFO queue.PriorityQueue - [Enqueue] 요소: 3 현재 대기열: [1,null,null,null,null,null,null,null,null,null,null]
17: 21:30.055 [main] INFO queue.PriorityQueue - [Enqueue] 현재 노드의 상위 노드 위치를 찾습니다. k: 1 상위: 0
17:21:30.056 [main] INFO queue.PriorityQueue - [큐 입력] 값 비교, 상위 노드: 1 대상 노드: 3
17:21:30.056 [main] INFO queue.PriorityQueue - [ 대기열 입력] Completed Idx: 1 Val: 3
현재 대기열: [1,3,null,null,null,null,null,null,null,null,null]
17:21:30.056 [main] INFO 대기열 .PriorityQueue - [Enqueue] 요소: 5 현재 대기열: [1,3,null,null,null,null,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - [ 큐에 들어가다] 현재 노드의 부모 노드 위치를 찾는다. k: 2 상위: 0
17:21:30.056 [main] INFO queue.PriorityQueue - [Enter queue] 값 비교, 상위 노드: 1 대상 노드: 5
17:21:30.056 [main] INFO queue.PriorityQueue - [ 대기열 입력] Completed Idx: 2 Val: 5
현재 대기열: [1,3,5,null,null,null,null,null,null,null,null]
17:21:30.056 [main] INFO 대기열 .PriorityQueue - [큐 입력] 요소: 11 현재 대기열: [1,3,5,null,null,null,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - [큐 입력] 현재 노드의 부모 노드 위치를 찾습니다. k: 3 상위: 1
17:21:30.056 [main] INFO queue.PriorityQueue - [Enter queue] 값 비교, 상위 노드: 3 대상 노드: 11
17:21:30.056 [main] INFO queue.PriorityQueue - [ 대기열 입력] Completed Idx: 3 Val: 11
현재 대기열: [1,3,5,11,null,null,null,null,null,null,null]
17:21:30.056 [main] INFO 대기열 .PriorityQueue - [Enqueue] 요소: 4 현재 대기열: [1,3,5,11,null,null,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - [ 큐에 들어가다] 현재 노드의 부모 노드 위치를 찾는다. k: 4 상위: 1
17:21:30.056 [main] INFO queue.PriorityQueue - [Enter queue] 값 비교, 상위 노드: 3 대상 노드: 4
17:21:30.056 [main] INFO queue.PriorityQueue - [ 대기열 입력] Completed Idx: 4 Val: 4
현재 대기열: [1,3,5,11,4,null,null,null,null,null,null]
17:21:30.056 [main] INFO 대기열 .PriorityQueue - [큐 입력] 요소: 6 현재 대기열: [1,3,5,11,4,null,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - [큐 입력] 현재 노드의 부모 노드 위치를 찾습니다. k: 5 상위: 2
17:21:30.056 [main] INFO queue.PriorityQueue - [큐 입력] 값 비교, 상위 노드: 5 대상 노드: 6
17:21:30.056 [main] INFO queue.PriorityQueue - [ 대기열 입력] Completed Idx: 5 Val: 6
현재 대기열: [1,3,5,11,4,6,null,null,null,null,null]
17:21:30.056 [main] INFO 대기열 .PriorityQueue - [큐 입력] 요소: 7 현재 대기열: [1,3,5,11,4,6,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - [큐 입력] 현재 노드의 부모 노드 위치를 찾습니다. k: 6 상위: 2
17:21:30.056 [main] INFO queue.PriorityQueue - [큐 입력] 값 비교, 상위 노드: 5 대상 노드: 7
17:21:30.056 [main] INFO queue.PriorityQueue - [ 대기열 입력] Completed Idx: 6 Val: 7
현재 대기열: [1,3,5,11,4,6,7,null,null,null,null] 17:21:30.056 [main] INFO 대기열.PriorityQueue - [큐 입력] 요소: 12 현재 큐: [1,3,5,11,4,6,7,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - [Enter 팀] 현재 노드의 부모 노드 위치를 찾습니다. k: 7 상위: 3
17:21:30.056 [main] INFO queue.PriorityQueue - [Enter queue] 값 비교, 상위 노드: 11 대상 노드: 12
17:21:30.056 [main] INFO queue.PriorityQueue - [ 대기열 입력] Completed Idx: 7 Val: 12
현재 대기열: [1,3,5,11,4,6,7,12,null,null,null]
17:21:30.056 [main] INFO 대기열 .PriorityQueue - [Enqueue] 요소: 15 현재 대기열: [1,3,5,11,4,6,7,12,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - [ 큐에 들어가다] 현재 노드의 부모 노드 위치를 찾는다. k: 8 상위: 3
17:21:30.056 [main] INFO queue.PriorityQueue - [큐 입력] 값 비교, 상위 노드: 11 대상 노드: 15
17:21:30.057 [main] INFO queue.PriorityQueue - [ 대기열 입력] Completed Idx: 8 Val: 15
현재 대기열: [1,3,5,11,4,6,7,12,15,null,null]
17:21:30.057 [main] INFO 대기열 .PriorityQueue - [Enqueue] 요소: 10 현재 대기열: [1,3,5,11,4,6,7,12,15,null,null]
17:21:30.057 [main] INFO queue.PriorityQueue - [ 큐에 들어가다] 현재 노드의 부모 노드 위치를 찾는다. k: 9 상위: 4
17:21:30.057 [main] INFO queue.PriorityQueue - [Enter queue] 값 비교, 상위 노드: 4 대상 노드: 10
17:21:30.057 [main] INFO queue.PriorityQueue - [ 대기열 입력] Completed Idx: 9 Val: 10
현재 대기열: [1,3,5,11,4,6,7,12,15,10,null]
17:21:30.057 [main] INFO 대기열 .PriorityQueue - [Enqueue] 요소: 9 현재 대기열: [1,3,5,11,4,6,7,12,15,10,null]
17:21:30.057 [main] INFO queue.PriorityQueue - [ 큐에 들어가다] 현재 노드의 부모 노드 위치를 찾는다. k:10 부모:4
17:21:30.057 [main] INFO queue.PriorityQueue - [Enter Queue] 값 비교, 상위 노드: 4 대상 노드: 9
17:21:30.057 [main] INFO queue.PriorityQueue - [Enter Queue] 완료 Idx: 10 Val: 9
현재 대기열: [1,3,5,11,4,6,7,12,15,10,9]
17:21:30.057 [main] INFO queue.PriorityQueue - [대기열 입력] 요소 : 8 현재 대기열: [1,3,5,11,4,6,7,12,15,10,9,null,null,null,null,null,null,null,null,null,null,null , null,null]
17:21:30.057 [main] INFO queue.PriorityQueue - [큐 입력] 현재 노드의 상위 노드 위치를 찾습니다. k: 11 상위: 5
17:21:30.057 [main] INFO queue.PriorityQueue - [Enter queue] 값 비교, 상위 노드: 6 대상 노드: 8
17:21:30.057 [main] INFO queue.PriorityQueue - [ 대기열 입력] Completed Idx: 11 Val: 8
현재 대기열: [1,3,5,11,4,6,7,12,15,10,9,8,null,null,null,null,null, null,null,null,null,null,null,null]
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 1 하위 노드: 3 위치 교체
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 왼쪽 및 오른쪽 하위 노드를 비교하여 최소값을 얻습니다. 왼쪽: 11 오른쪽: 4
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 3 하위 노드: 4 위치 교체
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 왼쪽 및 오른쪽 하위 노드를 비교하여 최소값을 얻습니다. 왼쪽: 10 오른쪽: 9
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 결과를 교체하고 마지막으로 위치를 변경합니다. Idx: 4 Val: 8
17:21:30.057 [main] INFO heap.__test__.HeapTest - 테스트 결과: 1
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 3 하위 노드: 4 위치 교체
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 왼쪽 및 오른쪽 하위 노드를 비교하여 최소값을 얻습니다. 왼쪽: 11 오른쪽: 8
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 4 하위 노드: 8 위치 교체
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 결과를 교체하고 최종적으로 위치를 변경합니다. Idx: 4 Val: 9
17:21:30.057 [main] INFO heap.__test__.HeapTest - 테스트 결과: 3
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 왼쪽 및 오른쪽 하위 노드 비교 , 최소값을 구하십시오. 왼쪽: 8 오른쪽: 5
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 4 하위 노드: 5 위치 교체
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 5 하위 노드: 6 위치 교체
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 결과를 교체하고 최종적으로 위치를 변경합니다. Idx: 5 Val: 10
17:21:30.057 [main] INFO heap.__test__.HeapTest - 테스트 결과: 4
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] 왼쪽 및 오른쪽 하위 노드 비교 , 최소값을 구하십시오. 왼쪽: 8 오른쪽: 6
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 5 하위 노드: 6 위치 교체
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 왼쪽 및 오른쪽 하위 노드를 비교하여 최소값을 얻습니다. 왼쪽: 10 오른쪽: 7
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 6 하위 노드: 7 위치 교체
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 결과를 교체하고 최종적으로 위치를 변경합니다. Idx: 6 Val: 15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 테스트 결과: 5
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 왼쪽 및 오른쪽 하위 노드 비교 , 최소값을 구하십시오. 왼쪽: 8 오른쪽: 7
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 6 하위 노드: 7 위치 교체
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 7 하위 노드: 10 위치 교체
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 결과를 교체하고 최종적으로 위치를 변경합니다. Idx: 5 Val: 12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 테스트 결과: 6
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 7 하위 노드: 8 위치 교체
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 왼쪽 및 오른쪽 하위 노드를 비교하여 최소값을 얻습니다. 왼쪽: 11 오른쪽: 9
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 8 하위 노드: 9 위치 교체
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 결과를 교체하고 최종적으로 위치를 변경합니다. Idx: 4 Val: 15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 테스트 결과: 7
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 8 하위 노드: 9 위치 교체
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 9 하위 노드: 11 위치 교체
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果,最终更换位置。Idx:3 Val:12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果:8
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】左右子节点比对,获取最小值。left:11 right:10
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程,节点的值比对。上节点:9 下节点:10 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果,最终更换位置。Idx:2 Val:15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果:9
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程,节点的值比对。上节点:10 下节点:11 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果,最终更换位置。Idx:1 Val:12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果:10
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程,节点的值比对。上节点:11 下节点:12 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果,最终更换位置。Idx:1 Val:15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果:11
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果,最终更换位置。Idx:0 Val:15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果:12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果:15
Process finished with exit code 0
小堆就是一个正序的输出结果,从小到大的排序和输出。
小堆空间:[1,3,5,11,4,6,7,12,15,10,9,8,null,null,null,null,null,null,null,null,null,null,null,null]
- 小堆就是一个正序的输出结果,从小到大的排序和输出。
- 小堆空间:[1,3,5,11,4,6,7,12,15,10,9,8,null,null,null,null,null,null,null,null,null,null,null,null]
5. 大堆实现
小堆是一个反序比对
public class MaxHeap extends Heap<Integer> { @Override public int compareTo(Integer firstElement, Integer secondElement) { return secondElement.compareTo(firstElement); } }
测试
@Test public void test_max_heap() { MaxHeap heap = new MaxHeap(); // 存入元素 heap.add(1); heap.add(3); heap.add(5); heap.add(11); heap.add(4); heap.add(6); heap.add(7); heap.add(12); heap.add(15); heap.add(10); heap.add(9); heap.add(8); // 弹出元素 while (heap.peek() != null){ logger.info("测试结果:{}", heap.poll()); } }
结果
17:23:45.079 [main] INFO queue.PriorityQueue - [Enqueue] 요소: 3 현재 대기열: [1,null,null,null,null,null,null,null,null,null,null]
17: 23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] 현재 노드의 상위 노드 위치를 찾습니다. k: 1 parent: 0
17:23:45.081 [main] INFO queue.PriorityQueue - [큐 입력] 교체 프로세스, 부모 및 자식 노드의 위치가 교체되고 주기가 계속됩니다. 상위 노드 값: 1 저장된 위치: 1
17:23:45.081 [main] INFO queue.PriorityQueue - [Enter queue] Completed Idx: 0 Val: 3
현재 대기열: [3,1,null,null,null, null,null,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] 요소: 5 현재 대기열: [3,1,null,null,null,null, null ,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue - [큐 입력] 현재 노드의 상위 노드 위치를 찾습니다. k: 2 parent: 0
17:23:45.081 [main] INFO queue.PriorityQueue - [큐 입력] 교체 프로세스, 부모 및 자식 노드의 위치가 교체되고 주기가 계속됩니다. 상위 노드 값: 3 저장된 위치: 2
17:23:45.081 [main] INFO queue.PriorityQueue - [큐 입력] Completed Idx: 0 Val: 5
현재 대기열: [5,1,3,null,null, null,null,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] 요소: 11 현재 대기열: [5,1,3,null,null,null, null ,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue - [큐 입력] 현재 노드의 상위 노드 위치를 찾습니다. k: 3 parent: 1
17:23:45.081 [main] INFO queue.PriorityQueue - [큐 입력] 교체 프로세스, 부모 및 자식 노드의 위치가 교체되고 주기가 계속됩니다. 상위 노드 값: 1 저장 위치: 3
17:23:45.081 [main] INFO queue.PriorityQueue - [큐 입력] 현재 노드의 상위 노드 위치를 찾습니다. k: 1 parent: 0
17:23:45.081 [main] INFO queue.PriorityQueue - [큐 입력] 교체 프로세스, 부모 및 자식 노드의 위치가 교체되고 주기가 계속됩니다. 상위 노드 값: 5 저장된 위치: 1
17:23:45.081 [main] INFO queue.PriorityQueue - [Enter queue] Completed Idx: 0 Val: 11
현재 대기열: [11,5,3,1,null, null,null,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] 요소: 4 현재 대기열: [11,5,3,1,null,null, null ,null,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - [큐 입력] 현재 노드의 상위 노드 위치를 찾습니다. k: 4 상위: 1
17:23:45.082 [main] INFO queue.PriorityQueue - [큐 입력] 값 비교, 상위 노드: 5 대상 노드: 4
17:23:45.082 [main] INFO queue.PriorityQueue - [ 대기열 입력] Completed Idx: 4 Val: 4
현재 대기열: [11,5,3,1,4,null,null,null,null,null,null]
17:23:45.082 [main] INFO 대기열 .PriorityQueue - [Enqueue] 요소: 6 현재 대기열: [11,5,3,1,4,null,null,null,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - [ 큐에 들어가다] 현재 노드의 부모 노드 위치를 찾는다. k: 5 parent: 2
17:23:45.082 [main] INFO queue.PriorityQueue - [큐 입력] 교체 프로세스, 부모 및 자식 노드의 위치가 교체되고 주기가 계속됩니다. 상위 노드 값: 3 저장된 위치: 5
17:23:45.082 [main] INFO queue.PriorityQueue - [큐 입력] 현재 노드의 상위 노드 위치를 찾습니다. k: 2 상위: 0
17:23:45.082 [main] INFO queue.PriorityQueue - [Enter queue] 값 비교, 상위 노드: 11 대상 노드: 6
17:23:45.082 [main] INFO queue.PriorityQueue - [ 대기열 입력] Completed Idx: 2 Val: 6
현재 대기열: [11,5,6,1,4,3,null,null,null,null,null]
17:23:45.082 [main] INFO 대기열 .PriorityQueue - [큐 입력] 요소: 7 현재 대기열: [11,5,6,1,4,3,null,null,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - [큐 입력] 현재 노드의 부모 노드 위치를 찾습니다. k: 6 parent: 2
17:23:45.082 [main] INFO queue.PriorityQueue - [큐 입력] 교체 프로세스, 부모 및 자식 노드의 위치가 교체되고 주기가 계속됩니다. 상위 노드 값 : 6 저장된 위치 : 6
17:23:45.082 [main] INFO queue.PriorityQueue - [큐 입력] 현재 노드의 상위 노드 위치를 찾습니다. k: 2 상위: 0
17:23:45.082 [main] INFO queue.PriorityQueue - [Enter queue] 값 비교, 상위 노드: 11 대상 노드: 7
17:23:45.082 [main] INFO queue.PriorityQueue - [ 대기열 입력] Completed Idx: 2 Val: 7
현재 대기열: [11,5,7,1,4,3,6,null,null,null,null]
17:23:45.082 [main] INFO 대기열 .PriorityQueue - [큐 입력] 요소: 12 현재 대기열: [11,5,7,1,4,3,6,null,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - [큐 입력] 현재 노드의 부모 노드 위치를 찾습니다. k: 7 parent: 3
17:23:45.082 [main] INFO queue.PriorityQueue - [큐 입력] 교체 프로세스, 부모 및 자식 노드의 위치가 교체되고 주기가 계속됩니다. 상위 노드 값: 1 저장 위치: 7
17:23:45.082 [main] INFO queue.PriorityQueue - [큐 입력] 현재 노드의 상위 노드 위치를 찾습니다. k: 3 parent: 1
17:23:45.082 [main] INFO queue.PriorityQueue - [큐 입력] 교체 프로세스, 부모 및 자식 노드의 위치가 교체되고 주기가 계속됩니다. 상위 노드 값: 5 저장된 위치: 3
17:23:45.082 [main] INFO queue.PriorityQueue - [큐 입력] 현재 노드의 상위 노드 위치를 찾습니다. k:부모 1명:0
17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] 교체 프로세스, 상위 및 하위 노드의 위치가 교체되고 주기가 계속됩니다. 상위 노드 값: 11 저장된 위치: 1
17:23:45.082 [main] INFO queue.PriorityQueue - [Enter queue] Completed Idx: 0 Val: 12
현재 대기열: [12,11,7,5,4, 3,6,1,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] 요소: 15 현재 대기열: [12,11,7,5,4,3, 6 ,1,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - [큐 입력] 현재 노드의 상위 노드 위치를 찾습니다. k: 8 parent: 3
17:23:45.082 [main] INFO queue.PriorityQueue - [큐 입력] 교체 프로세스, 부모 및 자식 노드의 위치가 교체되고 주기가 계속됩니다. 상위 노드 값: 5 저장된 위치: 8
17:23:45.082 [main] INFO queue.PriorityQueue - [큐 입력] 현재 노드의 상위 노드 위치를 찾습니다. k: 3 parent: 1
17:23:45.082 [main] INFO queue.PriorityQueue - [큐 입력] 교체 프로세스, 부모 및 자식 노드의 위치가 교체되고 주기가 계속됩니다. 상위 노드 값 : 11 저장 위치 : 3
17:23:45.082 [main] INFO queue.PriorityQueue - [큐 입력] 현재 노드의 상위 노드 위치를 찾습니다. k: 1 parent: 0
17:23:45.082 [main] INFO queue.PriorityQueue - [큐 입력] 교체 프로세스, 부모 및 자식 노드의 위치가 교체되고 주기가 계속됩니다. 상위 노드 값: 12 저장된 위치: 1
17:23:45.082 [main] INFO queue.PriorityQueue - [큐 입력] Completed Idx: 0 Val: 15
현재 대기열: [15,12,7,11,4, 3,6,1,5,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] 요소: 10 현재 대기열: [15,12,7,11,4,3, 6 ,1,5,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - [큐 입력] 현재 노드의 상위 노드 위치를 찾습니다. k: 9 parent: 4
17:23:45.083 [main] INFO queue.PriorityQueue - [큐 입력] 교체 프로세스, 부모 및 자식 노드의 위치가 교체되고 주기가 계속됩니다. 상위 노드 값: 4 저장 위치: 9
17:23:45.083 [main] INFO queue.PriorityQueue - [큐 입력] 현재 노드의 상위 노드 위치를 찾습니다. k: 4 상위: 1
17:23:45.083 [main] INFO queue.PriorityQueue - [Enter queue] 값 비교, 상위 노드: 12 대상 노드: 10
17:23:45.083 [main] INFO queue.PriorityQueue - [ 대기열 입력] Completed Idx: 4 Val: 10
현재 대기열: [15,12,7,11,10,3,6,1,5,4,null]
17:23:45.083 [main] INFO 대기열 .PriorityQueue - [Enqueue] 요소: 9 현재 대기열: [15,12,7,11,10,3,6,1,5,4,null]
17:23:45.083 [main] INFO queue.PriorityQueue - [ 큐에 들어가다] 현재 노드의 부모 노드 위치를 찾는다. k: 10 상위: 4
17:23:45.083 [main] INFO queue.PriorityQueue - [Enter queue] 값 비교, 상위 노드: 10 대상 노드: 9
17:23:45.083 [main] INFO queue.PriorityQueue - [ 대기열 입력] Completed Idx: 10 Val: 9
현재 대기열: [15,12,7,11,10,3,6,1,5,4,9]
17:23:45.083 [main] INFO 대기열 .PriorityQueue - [Enqueue] 요소: 8 현재 대기열: [15,12,7,11,10,3,6,1,5,4,9,null,null,null,null,null,null,null, null ,null,null,null,null,null]
17:23:45.083 [main] INFO queue.PriorityQueue - [Enqueue] 현재 노드의 상위 노드 위치를 찾습니다. k: 11 parent: 5
17:23:45.083 [main] INFO queue.PriorityQueue - [큐 입력] 교체 프로세스, 부모 및 자식 노드의 위치가 교체되고 주기가 계속됩니다. 상위 노드 값: 3 저장 위치: 11
17:23:45.083 [main] INFO queue.PriorityQueue - [큐 입력] 현재 노드의 상위 노드 위치를 찾습니다. k: 5 parent: 2
17:23:45.083 [main] INFO queue.PriorityQueue - [큐 입력] 교체 프로세스, 부모 및 자식 노드의 위치가 교체되고 주기가 계속됩니다. 상위 노드 값: 7 저장된 위치: 5
17:23:45.083 [main] INFO queue.PriorityQueue - [큐 입력] 현재 노드의 상위 노드 위치를 찾습니다. k: 2 상위: 0
17:23:45.083 [main] INFO queue.PriorityQueue - [Enter queue] 값 비교, 상위 노드: 15 대상 노드: 8
17:23:45.083 [main] INFO queue.PriorityQueue - [ 대기열 입력] Completed Idx: 2 Val: 8
현재 대기열: [15,12,8,11,10,7,6,1,5,4,9,3,null,null,null,null,null, null,null,null,null,null,null,null]
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 15 하위 노드: 12 위치 교체
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 12 하위 노드: 11 위치 교체
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 왼쪽 및 오른쪽 하위 노드를 비교하여 최소값을 얻습니다. 왼쪽: 1 오른쪽: 5
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 11 하위 노드: 5 위치 교체
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 결과를 교체하고 최종적으로 위치를 변경합니다. Idx: 8 Val: 3
17:23:45.083 [main] INFO heap.__test__.HeapTest - 테스트 결과: 15
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 12 하위 노드: 11 위치 교체
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 왼쪽 및 오른쪽 하위 노드를 비교하여 최소값을 얻습니다. 왼쪽:5 오른쪽:10
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 11 하위 노드: 10 위치 교체
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 결과를 교체하고 최종적으로 위치를 변경합니다. Idx: 4 Val: 9
17:23:45.083 [main] INFO heap.__test__.HeapTest - 테스트 결과: 12
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 11 하위 노드: 10 위치 교체
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 왼쪽 및 오른쪽 하위 노드를 비교하여 최소값을 얻습니다. 왼쪽: 5 오른쪽: 9
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 10 하위 노드: 9 위치 교체
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 결과를 교체하고 최종적으로 위치를 변경합니다. Idx: 4 Val: 4
17:23:45.083 [main] INFO heap.__test__.HeapTest - 테스트 결과: 11
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 10 하위 노드: 9 위치 교체
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 9 하위 노드: 5 위치 교체
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 결과를 교체하고 최종적으로 위치를 변경합니다. Idx: 3 Val: 3
17:23:45.084 [main] INFO heap.__test__.HeapTest - 테스트 결과: 10
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 왼쪽 및 오른쪽 하위 노드 비교 , 최소값을 구하십시오. 왼쪽: 5 오른쪽: 8
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 9 하위 노드: 8 위치 교체
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 8 하위 노드: 7 위치 교체
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 결과를 교체하고 최종적으로 위치를 변경합니다. Idx: 5 Val: 1
17:23:45.084 [main] INFO heap.__test__.HeapTest - 테스트 결과: 9
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 왼쪽 및 오른쪽 하위 노드 비교 , 최소값을 구하십시오. 왼쪽: 5 오른쪽: 7
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 8 하위 노드: 7 위치 교체
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 결과를 교체하고 최종적으로 위치를 변경합니다. Idx: 2 Val: 6
17:23:45.084 [main] INFO heap.__test__.HeapTest - 테스트 결과: 8
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 왼쪽 및 오른쪽 하위 노드 비교 , 최소값을 구하십시오. 왼쪽: 5 오른쪽: 6
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 7 하위 노드: 6 위치 교체
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 결과를 교체하고 최종적으로 위치를 변경합니다. Idx: 2 Val: 1
17:23:45.084 [main] INFO heap.__test__.HeapTest - 테스트 결과: 7
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 6 하위 노드: 5 위치 교체
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 결과를 교체하고 최종적으로 위치를 변경합니다. Idx: 1 Val: 4
17:23:45.084 [main] INFO heap.__test__.HeapTest - 테스트 결과: 6
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 5 하위 노드: 4 위치 교체
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 결과를 교체하고 최종적으로 위치를 변경합니다. Idx: 1 Val: 3
17:23:45.084 [main] INFO heap.__test__.HeapTest - 테스트 결과: 5
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 교체 프로세스, 노드 값 비교. 상위 노드: 4 하위 노드: 3 위치 교체
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 결과를 교체하고 최종적으로 위치를 변경합니다. Idx: 1 Val: 1
17:23:45.084 [main] INFO heap.__test__.HeapTest - 테스트 결과: 4
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] 교체 결과, 최종 교체 위치 . Idx: 0 Val: 1
17:23:45.084 [main] INFO heap.__test__.HeapTest - 테스트 결과: 3
17:23:45.084 [main] INFO heap.__test__.HeapTest - 테스트 결과: 1
Process done 종료 코드 0
큰 더미는 출력 결과를 역순으로 정렬하여 큰 것부터 작은 것 순으로 출력하는 것입니다.
큰 공간: [15,12,8,11,10,7,6,1,5,4,9,3,null,null,null,null,null,null,null,null,null,null , null,null]
추천 학습: "java 비디오 튜토리얼"
위 내용은 Java 데이터 구조의 최소 힙과 최대 힙의 원리와 구현에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

핫 AI 도구

Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

AI Hentai Generator
AI Hentai를 무료로 생성하십시오.

인기 기사

뜨거운 도구

메모장++7.3.1
사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전
중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경

드림위버 CS6
시각적 웹 개발 도구

SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)

뜨거운 주제











Java의 난수 생성기 안내. 여기서는 예제를 통해 Java의 함수와 예제를 통해 두 가지 다른 생성기에 대해 설명합니다.

Java의 Weka 가이드. 여기에서는 소개, weka java 사용 방법, 플랫폼 유형 및 장점을 예제와 함께 설명합니다.

자바의 암스트롱 번호 안내 여기에서는 일부 코드와 함께 Java의 Armstrong 번호에 대한 소개를 논의합니다.

Java의 Smith Number 가이드. 여기서는 정의, Java에서 스미스 번호를 확인하는 방법에 대해 논의합니다. 코드 구현의 예.

이 기사에서는 가장 많이 묻는 Java Spring 면접 질문과 자세한 답변을 보관했습니다. 그래야 면접에 합격할 수 있습니다.

Java 8은 스트림 API를 소개하여 데이터 컬렉션을 처리하는 강력하고 표현적인 방법을 제공합니다. 그러나 스트림을 사용할 때 일반적인 질문은 다음과 같은 것입니다. 기존 루프는 조기 중단 또는 반환을 허용하지만 스트림의 Foreach 메소드는이 방법을 직접 지원하지 않습니다. 이 기사는 이유를 설명하고 스트림 처리 시스템에서 조기 종료를 구현하기위한 대체 방법을 탐색합니다. 추가 읽기 : Java Stream API 개선 스트림 foreach를 이해하십시오 Foreach 메소드는 스트림의 각 요소에서 하나의 작업을 수행하는 터미널 작동입니다. 디자인 의도입니다
