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 중국어 웹사이트의 기타 관련 기사를 참조하세요!