HW)
연결리스트(Linked List)와 이진 트리(Binay Tree)에 이어서 자료 구조 관련하여 '힙(Heap)'에 대해서 이해해보자.
우선, 힙의 개념에 대해서 알아보자.
힙(Heap)
> 힙은 완전 이진 트리(Complete Binary Tree) 기반의 자료 구조로, 부모(Parent) 노드가 항상 자식(Child) 노드보다 크거나 작도록 (이상 또는 이하) 유지하는 형태를 말한다.
- 완전 이진 트리의 규칙 : 중간에 빈 노드 없이, 마지막 레벨(가장 아래 깊이)을 제외한 나머지 노드가 모두 차야한다.
- 힙에는 삽입 과정과 삭제 과정이 있다. 아래 표와 같이 정리해보자.
| 구분 | 힙 삽입(Insert) 과정 | 힙 삭제(Delete) 과정 |
| 규칙 | - 삽입 시 위로 끌어올림 (Heapify-up) - 마지막 위치에 새 원소 삽입 - 부모와 비교하며 위 레벨로 올리기 (Bubble Up) |
- 삭제 시 아래로 내림 (Heapify-down) - 마지막 원소를 root로 이동 - 아래로 내리며 정렬 (Heapify Down) - 루트(최댓값/최솟값)를 제거 |
- 또한, 힙에는 Max Heap과 Min Heap으로 구분된다. 아래와 같이 정리해보자.
| 구분 | Max Heap | Min Heap |
| 조건 (노드 값 크기 비교) |
부모 ≥ 자식 | 부모 ≤ 자식 |
| root에 위치한 값 | 최대값 | 최소값 |
| 규칙에 따른 연산 결과, 목록 출력 예시 | 시작 목록 : [5, 3, 8, 1, 7, 9, 2, 6, 4] → Max Heap PUSH (insert, 상향 종료 시) : [9, 7, 8, 6, 3, 5, 2, 1, 4] → Max Heap POP (delete, 하향 종료 시) : [9, 8, 7, 6, 5, 4, 3, 2, 1] → 최종 내림차순 정렬 |
시작 목록 : [5, 3, 8, 1, 7, 9, 2, 6, 4] → Min Heap PUSH (insert, 상향 종료 시) : [1, 3, 2, 4, 7, 9, 8, 6, 5] → Min Heap POP (delete, 하향 종료 시) : [1, 2, 3, 4, 5, 6, 7, 8, 9] → 최종 오름차순 정렬 |
- 아래 그림은 Max Heap과 Min Heap의 삽입(insert) 즉 상향 단계가 모두 종료되었을 때의 노드의 배치 구조이다. 이 결과는 각 경우에 대한 출력 결과를 재차 도식화 한 것이다. (아래, 코드 출력 결과 참조)
> 힙의 실제 프로그래밍에서 활용 사례
- 우선순위 큐 (Priority Queue) : √
- 힙 정렬 (Heap Sort) : √
- 스케줄링 알고리즘
- 다익스트라 최단경로 알고리즘 등
글로 설명하면 정말 이해하기 어렵다. 지난 트리의 구조를 코드 출력으로써 단계별로 확인하면서 이해했듯이, 이 번에도 동일한 방법으로 Max Heap과 Min Heap 각각의 경우에 대해서 삽입과 삭제 과정 단계를 하나씩 확인하면서 이해해보고자 한다. 이러한 경우는 우선순위 큐의 핵심 구현 원리이면서 동시에 힙 정렬의 핵심 단계라고 한다.
[출력 결과] MaxHeap의 삽입과 삭제 과정
> 초기 기준 데이터 목록은 1~9 숫자로 구성한 [5, 3, 8, 1, 7, 9, 2, 6, 4] 로 하였다.
- 가운데 숫자 5가 root이다.
> MaxHeap PUSH 즉 삽입(insert) 과정의 규칙:
- 부모 노드가 항상 자식보다 크거나 같은 값을 유지한다.
- 삽입 시 상향(bubble-up), 삭제 시 하향(heapify-down) 규칙을 적용한다.
- 비교 기준: parent < child → swap 실행 (큰 값이 위로 올라감)
'''
=== MaxHeap 애니메이션 ===
설명: MaxHeap은 부모 노드가 항상 자식보다 크거나 같은 값을 유지합니다.
삽입 시 상향(bubble-up), 삭제 시 하향(heapify-down) 규칙을 적용합니다.
비교 기준: parent < child → swap 실행 (큰 값이 위로 올라감)
설명: 아래 순서대로 삽입하며, 삽입 시마다 부모와 비교하여 상향 이동합니다.
삽입 데이터: [5, 3, 8, 1, 7, 9, 2, 6, 4]
=== MaxHeap PUSH: append 5 ===
[5]
배열 상태 (append 직후)
i:0
5
^
선택 기준: 부모와 현재 노드 비교
규칙: parent < child → swap (MaxHeap)
설명: 부모가 현재보다 작으면 상향 이동
=== MaxHeap PUSH: append 3 ===
5
---
[3]
배열 상태 (append 직후)
i:0 i:1
5 3
^
선택 기준: 부모와 현재 노드 비교
규칙: parent < child → swap (MaxHeap)
설명: 부모가 현재보다 작으면 상향 이동
=== MaxHeap PUSH: 비교 parent=5(i:0) vs cur=3(i:1) ===
(5)
---
[3]
배열 상태 (swap 전 비교)
i:0 i:1
5 3
• ^
선택 기준: 부모와 현재 노드 비교
규칙: parent < child → swap (MaxHeap)
판정: 교환 불필요 (규칙 만족)
=== MaxHeap PUSH: 상향 종료 (규칙 만족) ===
(5)
---
[3]
배열 상태 (상향 종료)
i:0 i:1
5 3
• ^
=== MaxHeap PUSH: append 8 ===
5
--- ---
3 [8]
배열 상태 (append 직후)
i:0 i:1 i:2
5 3 8
^
선택 기준: 부모와 현재 노드 비교
규칙: parent < child → swap (MaxHeap)
설명: 부모가 현재보다 작으면 상향 이동
=== MaxHeap PUSH: 비교 parent=5(i:0) vs cur=8(i:2) ===
(5)
--- ---
3 [8]
배열 상태 (swap 전 비교)
i:0 i:1 i:2
5 3 8
• ^
선택 기준: 부모와 현재 노드 비교
규칙: parent < child → swap (MaxHeap)
판정: 교환 필요 (규칙 위반)
=== MaxHeap PUSH: swap 실행 (i:0 ↔ i:2) ===
배열 상태 (swap 직전)
i:0 i:1 i:2
5 3 8
• ^
=== MaxHeap PUSH: swap 후 위치 i:0 ===
[8]
--- ---
3 5
배열 상태 (swap 직후)
i:0 i:1 i:2
8 3 5
^
=== MaxHeap PUSH: append 1 ===
8
----- -----
3 5
---
[1]
배열 상태 (append 직후)
i:0 i:1 i:2 i:3
8 3 5 1
^
선택 기준: 부모와 현재 노드 비교
규칙: parent < child → swap (MaxHeap)
설명: 부모가 현재보다 작으면 상향 이동
=== MaxHeap PUSH: 비교 parent=3(i:1) vs cur=1(i:3) ===
8
----- -----
(3) 5
---
[1]
배열 상태 (swap 전 비교)
i:0 i:1 i:2 i:3
8 3 5 1
• ^
선택 기준: 부모와 현재 노드 비교
규칙: parent < child → swap (MaxHeap)
판정: 교환 불필요 (규칙 만족)
=== MaxHeap PUSH: 상향 종료 (규칙 만족) ===
8
----- -----
(3) 5
---
[1]
배열 상태 (상향 종료)
i:0 i:1 i:2 i:3
8 3 5 1
• ^
=== MaxHeap PUSH: append 7 ===
8
----- -----
3 5
--- ---
1 [7]
배열 상태 (append 직후)
i:0 i:1 i:2 i:3 i:4
8 3 5 1 7
^
선택 기준: 부모와 현재 노드 비교
규칙: parent < child → swap (MaxHeap)
설명: 부모가 현재보다 작으면 상향 이동
=== MaxHeap PUSH: 비교 parent=3(i:1) vs cur=7(i:4) ===
8
----- -----
(3) 5
--- ---
1 [7]
배열 상태 (swap 전 비교)
i:0 i:1 i:2 i:3 i:4
8 3 5 1 7
• ^
선택 기준: 부모와 현재 노드 비교
규칙: parent < child → swap (MaxHeap)
판정: 교환 필요 (규칙 위반)
=== MaxHeap PUSH: swap 실행 (i:1 ↔ i:4) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3 i:4
8 3 5 1 7
• ^
=== MaxHeap PUSH: swap 후 위치 i:1 ===
8
----- -----
[7] 5
--- ---
1 3
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3 i:4
8 7 5 1 3
^
=== MaxHeap PUSH: 비교 parent=8(i:0) vs cur=7(i:1) ===
(8)
----- -----
[7] 5
--- ---
1 3
배열 상태 (swap 전 비교)
i:0 i:1 i:2 i:3 i:4
8 7 5 1 3
• ^
선택 기준: 부모와 현재 노드 비교
규칙: parent < child → swap (MaxHeap)
판정: 교환 불필요 (규칙 만족)
=== MaxHeap PUSH: 상향 종료 (규칙 만족) ===
(8)
----- -----
[7] 5
--- ---
1 3
배열 상태 (상향 종료)
i:0 i:1 i:2 i:3 i:4
8 7 5 1 3
• ^
=== MaxHeap PUSH: append 9 ===
8
----- -----
7 5
--- --- ---
1 3 [9]
배열 상태 (append 직후)
i:0 i:1 i:2 i:3 i:4 i:5
8 7 5 1 3 9
^
선택 기준: 부모와 현재 노드 비교
규칙: parent < child → swap (MaxHeap)
설명: 부모가 현재보다 작으면 상향 이동
=== MaxHeap PUSH: 비교 parent=5(i:2) vs cur=9(i:5) ===
8
----- -----
7 (5)
--- --- ---
1 3 [9]
배열 상태 (swap 전 비교)
i:0 i:1 i:2 i:3 i:4 i:5
8 7 5 1 3 9
• ^
선택 기준: 부모와 현재 노드 비교
규칙: parent < child → swap (MaxHeap)
판정: 교환 필요 (규칙 위반)
=== MaxHeap PUSH: swap 실행 (i:2 ↔ i:5) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3 i:4 i:5
8 7 5 1 3 9
• ^
=== MaxHeap PUSH: swap 후 위치 i:2 ===
8
----- -----
7 [9]
--- --- ---
1 3 5
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3 i:4 i:5
8 7 9 1 3 5
^
=== MaxHeap PUSH: 비교 parent=8(i:0) vs cur=9(i:2) ===
(8)
----- -----
7 [9]
--- --- ---
1 3 5
배열 상태 (swap 전 비교)
i:0 i:1 i:2 i:3 i:4 i:5
8 7 9 1 3 5
• ^
선택 기준: 부모와 현재 노드 비교
규칙: parent < child → swap (MaxHeap)
판정: 교환 필요 (규칙 위반)
=== MaxHeap PUSH: swap 실행 (i:0 ↔ i:2) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3 i:4 i:5
8 7 9 1 3 5
• ^
=== MaxHeap PUSH: swap 후 위치 i:0 ===
[9]
----- -----
7 8
--- --- ---
1 3 5
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3 i:4 i:5
9 7 8 1 3 5
^
=== MaxHeap PUSH: append 2 ===
9
----- -----
7 8
--- --- --- ---
1 3 5 [2]
배열 상태 (append 직후)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
9 7 8 1 3 5 2
^
선택 기준: 부모와 현재 노드 비교
규칙: parent < child → swap (MaxHeap)
설명: 부모가 현재보다 작으면 상향 이동
=== MaxHeap PUSH: 비교 parent=8(i:2) vs cur=2(i:6) ===
9
----- -----
7 (8)
--- --- --- ---
1 3 5 [2]
배열 상태 (swap 전 비교)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
9 7 8 1 3 5 2
• ^
선택 기준: 부모와 현재 노드 비교
규칙: parent < child → swap (MaxHeap)
판정: 교환 불필요 (규칙 만족)
=== MaxHeap PUSH: 상향 종료 (규칙 만족) ===
9
----- -----
7 (8)
--- --- --- ---
1 3 5 [2]
배열 상태 (상향 종료)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
9 7 8 1 3 5 2
• ^
=== MaxHeap PUSH: append 6 ===
9
---------- ----------
7 8
----- ----- ----- -----
1 3 5 2
---
[6]
배열 상태 (append 직후)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
9 7 8 1 3 5 2 6
^
선택 기준: 부모와 현재 노드 비교
규칙: parent < child → swap (MaxHeap)
설명: 부모가 현재보다 작으면 상향 이동
=== MaxHeap PUSH: 비교 parent=1(i:3) vs cur=6(i:7) ===
9
---------- ----------
7 8
----- ----- ----- -----
(1) 3 5 2
---
[6]
배열 상태 (swap 전 비교)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
9 7 8 1 3 5 2 6
• ^
선택 기준: 부모와 현재 노드 비교
규칙: parent < child → swap (MaxHeap)
판정: 교환 필요 (규칙 위반)
=== MaxHeap PUSH: swap 실행 (i:3 ↔ i:7) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
9 7 8 1 3 5 2 6
• ^
=== MaxHeap PUSH: swap 후 위치 i:3 ===
9
---------- ----------
7 8
----- ----- ----- -----
[6] 3 5 2
---
1
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
9 7 8 6 3 5 2 1
^
=== MaxHeap PUSH: 비교 parent=7(i:1) vs cur=6(i:3) ===
9
---------- ----------
(7) 8
----- ----- ----- -----
[6] 3 5 2
---
1
배열 상태 (swap 전 비교)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
9 7 8 6 3 5 2 1
• ^
선택 기준: 부모와 현재 노드 비교
규칙: parent < child → swap (MaxHeap)
판정: 교환 불필요 (규칙 만족)
=== MaxHeap PUSH: 상향 종료 (규칙 만족) ===
9
---------- ----------
(7) 8
----- ----- ----- -----
[6] 3 5 2
---
1
배열 상태 (상향 종료)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
9 7 8 6 3 5 2 1
• ^
=== MaxHeap PUSH: append 4 ===
9
---------- ----------
7 8
----- ----- ----- -----
6 3 5 2
--- ---
1 [4]
배열 상태 (append 직후)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7 i:8
9 7 8 6 3 5 2 1 4
^
선택 기준: 부모와 현재 노드 비교
규칙: parent < child → swap (MaxHeap)
설명: 부모가 현재보다 작으면 상향 이동
=== MaxHeap PUSH: 비교 parent=6(i:3) vs cur=4(i:8) ===
9
---------- ----------
7 8
----- ----- ----- -----
(6) 3 5 2
--- ---
1 [4]
배열 상태 (swap 전 비교)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7 i:8
9 7 8 6 3 5 2 1 4
• ^
선택 기준: 부모와 현재 노드 비교
규칙: parent < child → swap (MaxHeap)
판정: 교환 불필요 (규칙 만족)
=== MaxHeap PUSH: 상향 종료 (규칙 만족) ===
9
---------- ----------
7 8
----- ----- ----- -----
(6) 3 5 2
--- ---
1 [4]
배열 상태 (상향 종료)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7 i:8
9 7 8 6 3 5 2 1 4
• ^
****************************************************************************************************
'''
> Max Heap으로 삽입(insert) 과정이 모두 종료되면, 초기 목록 순서 [5, 3, 8, 1, 7, 9, 2, 6, 4] 가 아래와 같이 바뀌었고, 완전 이진 트리 구조 또한 위와 같음을 확인 할 수 있다.
- 초기 : [5, 3, 8, 1, 7, 9, 2, 6, 4] → [9, 7, 8, 6, 3, 5, 2, 1, 4] : Max Heap PUSH (상향 종료)
> 이제 최대값(root)를 하나씩 꺼내면서, 삭제(Delete) 즉 Max Heap POP 단계를 진행해보자.
'''
설명: 이제 최대값(루트)을 하나씩 꺼내며 pop 연산을 시각화합니다.
루트 제거 후 마지막 노드를 루트에 올리고, 자식과 비교하여 하향 교환합니다.
=== MaxHeap POP 단계: 현재 루트 9 ===
[9]
---------- ----------
7 8
----- ----- ----- -----
6 3 5 2
--- ---
1 4
배열 상태 (pop 전)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7 i:8
9 7 8 6 3 5 2 1 4
^
=== MaxHeap POP: pop=9, 루트에 마지막 값 배치 ===
[4]
---------- ----------
7 8
----- ----- ----- -----
6 3 5 2
---
1
배열 상태 (루트 교체 직후)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
4 7 8 6 3 5 2 1
^
누적 pop 순서: 9
=== MaxHeap POP: 하향 비교 parent=4(i:0) vs child=8(i:2) ===
[4]
---------- ----------
7 (8)
----- ----- ----- -----
6 3 5 2
---
1
배열 상태 (하향 비교)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
4 7 8 6 3 5 2 1
^ •
선택 기준: 더 큰 자식 선택 (MaxHeap)
규칙: parent < child → swap (Max)
판정: 교환 필요 (규칙 위반)
=== MaxHeap POP: swap 실행 (i:0 ↔ i:2) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
4 7 8 6 3 5 2 1
^ •
=== MaxHeap POP: swap 후 위치 i:2 ===
8
---------- ----------
7 [4]
----- ----- ----- -----
6 3 5 2
---
1
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
8 7 4 6 3 5 2 1
^
=== MaxHeap POP: 하향 비교 parent=4(i:2) vs child=5(i:5) ===
8
---------- ----------
7 [4]
----- ----- ----- -----
6 3 (5) 2
---
1
배열 상태 (하향 비교)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
8 7 4 6 3 5 2 1
^ •
선택 기준: 더 큰 자식 선택 (MaxHeap)
규칙: parent < child → swap (Max)
판정: 교환 필요 (규칙 위반)
=== MaxHeap POP: swap 실행 (i:2 ↔ i:5) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
8 7 4 6 3 5 2 1
^ •
=== MaxHeap POP: swap 후 위치 i:5 ===
8
---------- ----------
7 5
----- ----- ----- -----
6 3 [4] 2
---
1
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
8 7 5 6 3 4 2 1
^
=== MaxHeap POP 단계: 현재 루트 8 ===
[8]
---------- ----------
7 5
----- ----- ----- -----
6 3 4 2
---
1
배열 상태 (pop 전)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
8 7 5 6 3 4 2 1
^
=== MaxHeap POP: pop=8, 루트에 마지막 값 배치 ===
[1]
----- -----
7 5
--- --- --- ---
6 3 4 2
배열 상태 (루트 교체 직후)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
1 7 5 6 3 4 2
^
누적 pop 순서: 9 8
=== MaxHeap POP: 하향 비교 parent=1(i:0) vs child=7(i:1) ===
[1]
----- -----
(7) 5
--- --- --- ---
6 3 4 2
배열 상태 (하향 비교)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
1 7 5 6 3 4 2
^ •
선택 기준: 더 큰 자식 선택 (MaxHeap)
규칙: parent < child → swap (Max)
판정: 교환 필요 (규칙 위반)
=== MaxHeap POP: swap 실행 (i:0 ↔ i:1) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
1 7 5 6 3 4 2
^ •
=== MaxHeap POP: swap 후 위치 i:1 ===
7
----- -----
[1] 5
--- --- --- ---
6 3 4 2
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
7 1 5 6 3 4 2
^
=== MaxHeap POP: 하향 비교 parent=1(i:1) vs child=6(i:3) ===
7
----- -----
[1] 5
--- --- --- ---
(6) 3 4 2
배열 상태 (하향 비교)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
7 1 5 6 3 4 2
^ •
선택 기준: 더 큰 자식 선택 (MaxHeap)
규칙: parent < child → swap (Max)
판정: 교환 필요 (규칙 위반)
=== MaxHeap POP: swap 실행 (i:1 ↔ i:3) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
7 1 5 6 3 4 2
^ •
=== MaxHeap POP: swap 후 위치 i:3 ===
7
----- -----
6 5
--- --- --- ---
[1] 3 4 2
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
7 6 5 1 3 4 2
^
=== MaxHeap POP 단계: 현재 루트 7 ===
[7]
----- -----
6 5
--- --- --- ---
1 3 4 2
배열 상태 (pop 전)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
7 6 5 1 3 4 2
^
=== MaxHeap POP: pop=7, 루트에 마지막 값 배치 ===
[2]
----- -----
6 5
--- --- ---
1 3 4
배열 상태 (루트 교체 직후)
i:0 i:1 i:2 i:3 i:4 i:5
2 6 5 1 3 4
^
누적 pop 순서: 9 8 7
=== MaxHeap POP: 하향 비교 parent=2(i:0) vs child=6(i:1) ===
[2]
----- -----
(6) 5
--- --- ---
1 3 4
배열 상태 (하향 비교)
i:0 i:1 i:2 i:3 i:4 i:5
2 6 5 1 3 4
^ •
선택 기준: 더 큰 자식 선택 (MaxHeap)
규칙: parent < child → swap (Max)
판정: 교환 필요 (규칙 위반)
=== MaxHeap POP: swap 실행 (i:0 ↔ i:1) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3 i:4 i:5
2 6 5 1 3 4
^ •
=== MaxHeap POP: swap 후 위치 i:1 ===
6
----- -----
[2] 5
--- --- ---
1 3 4
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3 i:4 i:5
6 2 5 1 3 4
^
=== MaxHeap POP: 하향 비교 parent=2(i:1) vs child=3(i:4) ===
6
----- -----
[2] 5
--- --- ---
1 (3) 4
배열 상태 (하향 비교)
i:0 i:1 i:2 i:3 i:4 i:5
6 2 5 1 3 4
^ •
선택 기준: 더 큰 자식 선택 (MaxHeap)
규칙: parent < child → swap (Max)
판정: 교환 필요 (규칙 위반)
=== MaxHeap POP: swap 실행 (i:1 ↔ i:4) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3 i:4 i:5
6 2 5 1 3 4
^ •
=== MaxHeap POP: swap 후 위치 i:4 ===
6
----- -----
3 5
--- --- ---
1 [2] 4
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3 i:4 i:5
6 3 5 1 2 4
^
=== MaxHeap POP 단계: 현재 루트 6 ===
[6]
----- -----
3 5
--- --- ---
1 2 4
배열 상태 (pop 전)
i:0 i:1 i:2 i:3 i:4 i:5
6 3 5 1 2 4
^
=== MaxHeap POP: pop=6, 루트에 마지막 값 배치 ===
[4]
----- -----
3 5
--- ---
1 2
배열 상태 (루트 교체 직후)
i:0 i:1 i:2 i:3 i:4
4 3 5 1 2
^
누적 pop 순서: 9 8 7 6
=== MaxHeap POP: 하향 비교 parent=4(i:0) vs child=5(i:2) ===
[4]
----- -----
3 (5)
--- ---
1 2
배열 상태 (하향 비교)
i:0 i:1 i:2 i:3 i:4
4 3 5 1 2
^ •
선택 기준: 더 큰 자식 선택 (MaxHeap)
규칙: parent < child → swap (Max)
판정: 교환 필요 (규칙 위반)
=== MaxHeap POP: swap 실행 (i:0 ↔ i:2) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3 i:4
4 3 5 1 2
^ •
=== MaxHeap POP: swap 후 위치 i:2 ===
5
----- -----
3 [4]
--- ---
1 2
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3 i:4
5 3 4 1 2
^
=== MaxHeap POP 단계: 현재 루트 5 ===
[5]
----- -----
3 4
--- ---
1 2
배열 상태 (pop 전)
i:0 i:1 i:2 i:3 i:4
5 3 4 1 2
^
=== MaxHeap POP: pop=5, 루트에 마지막 값 배치 ===
[2]
----- -----
3 4
---
1
배열 상태 (루트 교체 직후)
i:0 i:1 i:2 i:3
2 3 4 1
^
누적 pop 순서: 9 8 7 6 5
=== MaxHeap POP: 하향 비교 parent=2(i:0) vs child=4(i:2) ===
[2]
----- -----
3 (4)
---
1
배열 상태 (하향 비교)
i:0 i:1 i:2 i:3
2 3 4 1
^ •
선택 기준: 더 큰 자식 선택 (MaxHeap)
규칙: parent < child → swap (Max)
판정: 교환 필요 (규칙 위반)
=== MaxHeap POP: swap 실행 (i:0 ↔ i:2) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3
2 3 4 1
^ •
=== MaxHeap POP: swap 후 위치 i:2 ===
4
----- -----
3 [2]
---
1
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3
4 3 2 1
^
=== MaxHeap POP 단계: 현재 루트 4 ===
[4]
----- -----
3 2
---
1
배열 상태 (pop 전)
i:0 i:1 i:2 i:3
4 3 2 1
^
=== MaxHeap POP: pop=4, 루트에 마지막 값 배치 ===
[1]
--- ---
3 2
배열 상태 (루트 교체 직후)
i:0 i:1 i:2
1 3 2
^
누적 pop 순서: 9 8 7 6 5 4
=== MaxHeap POP: 하향 비교 parent=1(i:0) vs child=3(i:1) ===
[1]
--- ---
(3) 2
배열 상태 (하향 비교)
i:0 i:1 i:2
1 3 2
^ •
선택 기준: 더 큰 자식 선택 (MaxHeap)
규칙: parent < child → swap (Max)
판정: 교환 필요 (규칙 위반)
=== MaxHeap POP: swap 실행 (i:0 ↔ i:1) ===
배열 상태 (swap 직전)
i:0 i:1 i:2
1 3 2
^ •
=== MaxHeap POP: swap 후 위치 i:1 ===
3
--- ---
[1] 2
배열 상태 (swap 직후)
i:0 i:1 i:2
3 1 2
^
=== MaxHeap POP 단계: 현재 루트 3 ===
[3]
--- ---
1 2
배열 상태 (pop 전)
i:0 i:1 i:2
3 1 2
^
=== MaxHeap POP: pop=3, 루트에 마지막 값 배치 ===
[2]
---
1
배열 상태 (루트 교체 직후)
i:0 i:1
2 1
^
누적 pop 순서: 9 8 7 6 5 4 3
=== MaxHeap POP: 하향 비교 parent=2(i:0) vs child=1(i:1) ===
[2]
---
(1)
배열 상태 (하향 비교)
i:0 i:1
2 1
^ •
선택 기준: 더 큰 자식 선택 (MaxHeap)
규칙: parent < child → swap (Max)
판정: 교환 불필요 (규칙 만족)
=== MaxHeap POP: 하향 종료 (규칙 만족) ===
[2]
---
1
배열 상태 (하향 종료)
i:0 i:1
2 1
^
누적 pop 순서: 9 8 7 6 5 4 3
=== MaxHeap POP 단계: 현재 루트 2 ===
[2]
---
1
배열 상태 (pop 전)
i:0 i:1
2 1
^
=== MaxHeap POP: pop=2, 루트에 마지막 값 배치 ===
[1]
배열 상태 (루트 교체 직후)
i:0
1
^
누적 pop 순서: 9 8 7 6 5 4 3 2
=== MaxHeap POP 단계: 현재 루트 1 ===
[1]
배열 상태 (pop 전)
i:0
1
^
=== MaxHeap POP: pop=1, 루트에 마지막 값 배치 ===
(empty)
배열 상태 (루트 교체 직후)
(empty)
누적 pop 순서: 9 8 7 6 5 4 3 2 1
최종 pop 순서: 9 8 7 6 5 4 3 2 1
****************************************************************************************************
'''
> Max Heap POP 과정이 모두 끝났다.
- 최종 POP 목록이 9에서 1까지 내림차순 정렬이 되었다.
- 초기 : [5, 3, 8, 1, 7, 9, 2, 6, 4] → [9, 7, 8, 6, 3, 5, 2, 1, 4] : Max Heap PUSH (상향 종료) → 최종 : [9, 8, 7, 6, 5, 4, 3, 2, 1] : Max Heap POP (하향 종료)
다음으로, MinHeap의 경우를 이해해보자.
[출력 결과] MinHeap의 삽입과 삭제 과정
> 초기 기준 데이터 목록은 동일하다 : [5, 3, 8, 1, 7, 9, 2, 6, 4]
- 동일하게 숫자 5가 root이다.
> MinHeap PUSH 즉 삽입(insert) 과정의 규칙:
- 부모 노드가 항상 자식보다 작거나 같은 값을 유지한다.
- 삽입 시 상향(bubble-up), 삭제 시 하향(heapify-down) 규칙을 적용한다.
- 비교 기준: parent > child → swap 실행 (작은 값이 위로 올라감)
'''
=== MinHeap 애니메이션 ===
설명: MinHeap은 부모 노드가 항상 자식보다 작거나 같은 값을 유지합니다.
삽입 시 상향(bubble-up), 삭제 시 하향(heapify-down) 규칙을 적용합니다.
비교 기준: parent > child → swap 실행 (작은 값이 위로 올라감)
설명: 아래 순서대로 삽입하며, 삽입 시마다 부모와 비교하여 상향 이동합니다.
삽입 데이터: [5, 3, 8, 1, 7, 9, 2, 6, 4]
=== MinHeap PUSH: append 5 ===
[5]
배열 상태 (append 직후)
i:0
5
^
선택 기준: 부모와 현재 노드 비교
규칙: parent > child → swap (MinHeap)
설명: 부모가 현재보다 크면 상향 이동
=== MinHeap PUSH: append 3 ===
5
---
[3]
배열 상태 (append 직후)
i:0 i:1
5 3
^
선택 기준: 부모와 현재 노드 비교
규칙: parent > child → swap (MinHeap)
설명: 부모가 현재보다 크면 상향 이동
=== MinHeap PUSH: 비교 parent=5(i:0) vs cur=3(i:1) ===
(5)
---
[3]
배열 상태 (swap 전 비교)
i:0 i:1
5 3
• ^
선택 기준: 부모와 현재 노드 비교
규칙: parent > child → swap (MinHeap)
판정: 교환 필요 (규칙 위반)
=== MinHeap PUSH: swap 실행 (i:0 ↔ i:1) ===
배열 상태 (swap 직전)
i:0 i:1
5 3
• ^
=== MinHeap PUSH: swap 후 위치 i:0 ===
[3]
---
5
배열 상태 (swap 직후)
i:0 i:1
3 5
^
=== MinHeap PUSH: append 8 ===
3
--- ---
5 [8]
배열 상태 (append 직후)
i:0 i:1 i:2
3 5 8
^
선택 기준: 부모와 현재 노드 비교
규칙: parent > child → swap (MinHeap)
설명: 부모가 현재보다 크면 상향 이동
=== MinHeap PUSH: 비교 parent=3(i:0) vs cur=8(i:2) ===
(3)
--- ---
5 [8]
배열 상태 (swap 전 비교)
i:0 i:1 i:2
3 5 8
• ^
선택 기준: 부모와 현재 노드 비교
규칙: parent > child → swap (MinHeap)
판정: 교환 불필요 (규칙 만족)
=== MinHeap PUSH: 상향 종료 (규칙 만족) ===
(3)
--- ---
5 [8]
배열 상태 (상향 종료)
i:0 i:1 i:2
3 5 8
• ^
=== MinHeap PUSH: append 1 ===
3
----- -----
5 8
---
[1]
배열 상태 (append 직후)
i:0 i:1 i:2 i:3
3 5 8 1
^
선택 기준: 부모와 현재 노드 비교
규칙: parent > child → swap (MinHeap)
설명: 부모가 현재보다 크면 상향 이동
=== MinHeap PUSH: 비교 parent=5(i:1) vs cur=1(i:3) ===
3
----- -----
(5) 8
---
[1]
배열 상태 (swap 전 비교)
i:0 i:1 i:2 i:3
3 5 8 1
• ^
선택 기준: 부모와 현재 노드 비교
규칙: parent > child → swap (MinHeap)
판정: 교환 필요 (규칙 위반)
=== MinHeap PUSH: swap 실행 (i:1 ↔ i:3) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3
3 5 8 1
• ^
=== MinHeap PUSH: swap 후 위치 i:1 ===
3
----- -----
[1] 8
---
5
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3
3 1 8 5
^
=== MinHeap PUSH: 비교 parent=3(i:0) vs cur=1(i:1) ===
(3)
----- -----
[1] 8
---
5
배열 상태 (swap 전 비교)
i:0 i:1 i:2 i:3
3 1 8 5
• ^
선택 기준: 부모와 현재 노드 비교
규칙: parent > child → swap (MinHeap)
판정: 교환 필요 (규칙 위반)
=== MinHeap PUSH: swap 실행 (i:0 ↔ i:1) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3
3 1 8 5
• ^
=== MinHeap PUSH: swap 후 위치 i:0 ===
[1]
----- -----
3 8
---
5
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3
1 3 8 5
^
=== MinHeap PUSH: append 7 ===
1
----- -----
3 8
--- ---
5 [7]
배열 상태 (append 직후)
i:0 i:1 i:2 i:3 i:4
1 3 8 5 7
^
선택 기준: 부모와 현재 노드 비교
규칙: parent > child → swap (MinHeap)
설명: 부모가 현재보다 크면 상향 이동
=== MinHeap PUSH: 비교 parent=3(i:1) vs cur=7(i:4) ===
1
----- -----
(3) 8
--- ---
5 [7]
배열 상태 (swap 전 비교)
i:0 i:1 i:2 i:3 i:4
1 3 8 5 7
• ^
선택 기준: 부모와 현재 노드 비교
규칙: parent > child → swap (MinHeap)
판정: 교환 불필요 (규칙 만족)
=== MinHeap PUSH: 상향 종료 (규칙 만족) ===
1
----- -----
(3) 8
--- ---
5 [7]
배열 상태 (상향 종료)
i:0 i:1 i:2 i:3 i:4
1 3 8 5 7
• ^
=== MinHeap PUSH: append 9 ===
1
----- -----
3 8
--- --- ---
5 7 [9]
배열 상태 (append 직후)
i:0 i:1 i:2 i:3 i:4 i:5
1 3 8 5 7 9
^
선택 기준: 부모와 현재 노드 비교
규칙: parent > child → swap (MinHeap)
설명: 부모가 현재보다 크면 상향 이동
=== MinHeap PUSH: 비교 parent=8(i:2) vs cur=9(i:5) ===
1
----- -----
3 (8)
--- --- ---
5 7 [9]
배열 상태 (swap 전 비교)
i:0 i:1 i:2 i:3 i:4 i:5
1 3 8 5 7 9
• ^
선택 기준: 부모와 현재 노드 비교
규칙: parent > child → swap (MinHeap)
판정: 교환 불필요 (규칙 만족)
=== MinHeap PUSH: 상향 종료 (규칙 만족) ===
1
----- -----
3 (8)
--- --- ---
5 7 [9]
배열 상태 (상향 종료)
i:0 i:1 i:2 i:3 i:4 i:5
1 3 8 5 7 9
• ^
=== MinHeap PUSH: append 2 ===
1
----- -----
3 8
--- --- --- ---
5 7 9 [2]
배열 상태 (append 직후)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
1 3 8 5 7 9 2
^
선택 기준: 부모와 현재 노드 비교
규칙: parent > child → swap (MinHeap)
설명: 부모가 현재보다 크면 상향 이동
=== MinHeap PUSH: 비교 parent=8(i:2) vs cur=2(i:6) ===
1
----- -----
3 (8)
--- --- --- ---
5 7 9 [2]
배열 상태 (swap 전 비교)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
1 3 8 5 7 9 2
• ^
선택 기준: 부모와 현재 노드 비교
규칙: parent > child → swap (MinHeap)
판정: 교환 필요 (규칙 위반)
=== MinHeap PUSH: swap 실행 (i:2 ↔ i:6) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
1 3 8 5 7 9 2
• ^
=== MinHeap PUSH: swap 후 위치 i:2 ===
1
----- -----
3 [2]
--- --- --- ---
5 7 9 8
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
1 3 2 5 7 9 8
^
=== MinHeap PUSH: 비교 parent=1(i:0) vs cur=2(i:2) ===
(1)
----- -----
3 [2]
--- --- --- ---
5 7 9 8
배열 상태 (swap 전 비교)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
1 3 2 5 7 9 8
• ^
선택 기준: 부모와 현재 노드 비교
규칙: parent > child → swap (MinHeap)
판정: 교환 불필요 (규칙 만족)
=== MinHeap PUSH: 상향 종료 (규칙 만족) ===
(1)
----- -----
3 [2]
--- --- --- ---
5 7 9 8
배열 상태 (상향 종료)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
1 3 2 5 7 9 8
• ^
=== MinHeap PUSH: append 6 ===
1
---------- ----------
3 2
----- ----- ----- -----
5 7 9 8
---
[6]
배열 상태 (append 직후)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
1 3 2 5 7 9 8 6
^
선택 기준: 부모와 현재 노드 비교
규칙: parent > child → swap (MinHeap)
설명: 부모가 현재보다 크면 상향 이동
=== MinHeap PUSH: 비교 parent=5(i:3) vs cur=6(i:7) ===
1
---------- ----------
3 2
----- ----- ----- -----
(5) 7 9 8
---
[6]
배열 상태 (swap 전 비교)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
1 3 2 5 7 9 8 6
• ^
선택 기준: 부모와 현재 노드 비교
규칙: parent > child → swap (MinHeap)
판정: 교환 불필요 (규칙 만족)
=== MinHeap PUSH: 상향 종료 (규칙 만족) ===
1
---------- ----------
3 2
----- ----- ----- -----
(5) 7 9 8
---
[6]
배열 상태 (상향 종료)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
1 3 2 5 7 9 8 6
• ^
=== MinHeap PUSH: append 4 ===
1
---------- ----------
3 2
----- ----- ----- -----
5 7 9 8
--- ---
6 [4]
배열 상태 (append 직후)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7 i:8
1 3 2 5 7 9 8 6 4
^
선택 기준: 부모와 현재 노드 비교
규칙: parent > child → swap (MinHeap)
설명: 부모가 현재보다 크면 상향 이동
=== MinHeap PUSH: 비교 parent=5(i:3) vs cur=4(i:8) ===
1
---------- ----------
3 2
----- ----- ----- -----
(5) 7 9 8
--- ---
6 [4]
배열 상태 (swap 전 비교)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7 i:8
1 3 2 5 7 9 8 6 4
• ^
선택 기준: 부모와 현재 노드 비교
규칙: parent > child → swap (MinHeap)
판정: 교환 필요 (규칙 위반)
=== MinHeap PUSH: swap 실행 (i:3 ↔ i:8) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7 i:8
1 3 2 5 7 9 8 6 4
• ^
=== MinHeap PUSH: swap 후 위치 i:3 ===
1
---------- ----------
3 2
----- ----- ----- -----
[4] 7 9 8
--- ---
6 5
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7 i:8
1 3 2 4 7 9 8 6 5
^
=== MinHeap PUSH: 비교 parent=3(i:1) vs cur=4(i:3) ===
1
---------- ----------
(3) 2
----- ----- ----- -----
[4] 7 9 8
--- ---
6 5
배열 상태 (swap 전 비교)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7 i:8
1 3 2 4 7 9 8 6 5
• ^
선택 기준: 부모와 현재 노드 비교
규칙: parent > child → swap (MinHeap)
판정: 교환 불필요 (규칙 만족)
=== MinHeap PUSH: 상향 종료 (규칙 만족) ===
1
---------- ----------
(3) 2
----- ----- ----- -----
[4] 7 9 8
--- ---
6 5
배열 상태 (상향 종료)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7 i:8
1 3 2 4 7 9 8 6 5
• ^
****************************************************************************************************
'''
> Min Heap으로 삽입(insert) 과정이 모두 종료되면, 초기 목록 순서 [5, 3, 8, 1, 7, 9, 2, 6, 4] 가 아래와 같이 바뀌었고, 완전 이진 트리 구조 또한 위와 같음을 확인 할 수 있다.
- 초기 : [5, 3, 8, 1, 7, 9, 2, 6, 4] → [1, 3, 2, 4, 7, 9, 8, 6, 5] : Min Heap PUSH (상향 종료)
> 이제 최대값(root)를 하나씩 꺼내면서, 삭제(Delete) 즉 Min Heap POP 단계를 진행해보자.
'''
설명: 이제 최소값(루트)을 하나씩 꺼내며 pop 연산을 시각화합니다.
루트 제거 후 마지막 노드를 루트에 올리고, 자식과 비교하여 하향 교환합니다.
=== MinHeap POP 단계: 현재 루트 1 ===
[1]
---------- ----------
3 2
----- ----- ----- -----
4 7 9 8
--- ---
6 5
배열 상태 (pop 전)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7 i:8
1 3 2 4 7 9 8 6 5
^
=== MinHeap POP: pop=1, 루트에 마지막 값 배치 ===
[5]
---------- ----------
3 2
----- ----- ----- -----
4 7 9 8
---
6
배열 상태 (루트 교체 직후)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
5 3 2 4 7 9 8 6
^
누적 pop 순서: 1
=== MinHeap POP: 하향 비교 parent=5(i:0) vs child=2(i:2) ===
[5]
---------- ----------
3 (2)
----- ----- ----- -----
4 7 9 8
---
6
배열 상태 (하향 비교)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
5 3 2 4 7 9 8 6
^ •
선택 기준: 더 작은 자식 선택 (MinHeap)
규칙: parent > child → swap (Min)
판정: 교환 필요 (규칙 위반)
=== MinHeap POP: swap 실행 (i:0 ↔ i:2) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
5 3 2 4 7 9 8 6
^ •
=== MinHeap POP: swap 후 위치 i:2 ===
2
---------- ----------
3 [5]
----- ----- ----- -----
4 7 9 8
---
6
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
2 3 5 4 7 9 8 6
^
=== MinHeap POP: 하향 비교 parent=5(i:2) vs child=8(i:6) ===
2
---------- ----------
3 [5]
----- ----- ----- -----
4 7 9 (8)
---
6
배열 상태 (하향 비교)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
2 3 5 4 7 9 8 6
^ •
선택 기준: 더 작은 자식 선택 (MinHeap)
규칙: parent > child → swap (Min)
판정: 교환 불필요 (규칙 만족)
=== MinHeap POP: 하향 종료 (규칙 만족) ===
2
---------- ----------
3 [5]
----- ----- ----- -----
4 7 9 8
---
6
배열 상태 (하향 종료)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
2 3 5 4 7 9 8 6
^
누적 pop 순서: 1
=== MinHeap POP 단계: 현재 루트 2 ===
[2]
---------- ----------
3 5
----- ----- ----- -----
4 7 9 8
---
6
배열 상태 (pop 전)
i:0 i:1 i:2 i:3 i:4 i:5 i:6 i:7
2 3 5 4 7 9 8 6
^
=== MinHeap POP: pop=2, 루트에 마지막 값 배치 ===
[6]
----- -----
3 5
--- --- --- ---
4 7 9 8
배열 상태 (루트 교체 직후)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
6 3 5 4 7 9 8
^
누적 pop 순서: 1 2
=== MinHeap POP: 하향 비교 parent=6(i:0) vs child=3(i:1) ===
[6]
----- -----
(3) 5
--- --- --- ---
4 7 9 8
배열 상태 (하향 비교)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
6 3 5 4 7 9 8
^ •
선택 기준: 더 작은 자식 선택 (MinHeap)
규칙: parent > child → swap (Min)
판정: 교환 필요 (규칙 위반)
=== MinHeap POP: swap 실행 (i:0 ↔ i:1) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
6 3 5 4 7 9 8
^ •
=== MinHeap POP: swap 후 위치 i:1 ===
3
----- -----
[6] 5
--- --- --- ---
4 7 9 8
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
3 6 5 4 7 9 8
^
=== MinHeap POP: 하향 비교 parent=6(i:1) vs child=4(i:3) ===
3
----- -----
[6] 5
--- --- --- ---
(4) 7 9 8
배열 상태 (하향 비교)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
3 6 5 4 7 9 8
^ •
선택 기준: 더 작은 자식 선택 (MinHeap)
규칙: parent > child → swap (Min)
판정: 교환 필요 (규칙 위반)
=== MinHeap POP: swap 실행 (i:1 ↔ i:3) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
3 6 5 4 7 9 8
^ •
=== MinHeap POP: swap 후 위치 i:3 ===
3
----- -----
4 5
--- --- --- ---
[6] 7 9 8
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
3 4 5 6 7 9 8
^
=== MinHeap POP 단계: 현재 루트 3 ===
[3]
----- -----
4 5
--- --- --- ---
6 7 9 8
배열 상태 (pop 전)
i:0 i:1 i:2 i:3 i:4 i:5 i:6
3 4 5 6 7 9 8
^
=== MinHeap POP: pop=3, 루트에 마지막 값 배치 ===
[8]
----- -----
4 5
--- --- ---
6 7 9
배열 상태 (루트 교체 직후)
i:0 i:1 i:2 i:3 i:4 i:5
8 4 5 6 7 9
^
누적 pop 순서: 1 2 3
=== MinHeap POP: 하향 비교 parent=8(i:0) vs child=4(i:1) ===
[8]
----- -----
(4) 5
--- --- ---
6 7 9
배열 상태 (하향 비교)
i:0 i:1 i:2 i:3 i:4 i:5
8 4 5 6 7 9
^ •
선택 기준: 더 작은 자식 선택 (MinHeap)
규칙: parent > child → swap (Min)
판정: 교환 필요 (규칙 위반)
=== MinHeap POP: swap 실행 (i:0 ↔ i:1) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3 i:4 i:5
8 4 5 6 7 9
^ •
=== MinHeap POP: swap 후 위치 i:1 ===
4
----- -----
[8] 5
--- --- ---
6 7 9
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3 i:4 i:5
4 8 5 6 7 9
^
=== MinHeap POP: 하향 비교 parent=8(i:1) vs child=6(i:3) ===
4
----- -----
[8] 5
--- --- ---
(6) 7 9
배열 상태 (하향 비교)
i:0 i:1 i:2 i:3 i:4 i:5
4 8 5 6 7 9
^ •
선택 기준: 더 작은 자식 선택 (MinHeap)
규칙: parent > child → swap (Min)
판정: 교환 필요 (규칙 위반)
=== MinHeap POP: swap 실행 (i:1 ↔ i:3) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3 i:4 i:5
4 8 5 6 7 9
^ •
=== MinHeap POP: swap 후 위치 i:3 ===
4
----- -----
6 5
--- --- ---
[8] 7 9
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3 i:4 i:5
4 6 5 8 7 9
^
=== MinHeap POP 단계: 현재 루트 4 ===
[4]
----- -----
6 5
--- --- ---
8 7 9
배열 상태 (pop 전)
i:0 i:1 i:2 i:3 i:4 i:5
4 6 5 8 7 9
^
=== MinHeap POP: pop=4, 루트에 마지막 값 배치 ===
[9]
----- -----
6 5
--- ---
8 7
배열 상태 (루트 교체 직후)
i:0 i:1 i:2 i:3 i:4
9 6 5 8 7
^
누적 pop 순서: 1 2 3 4
=== MinHeap POP: 하향 비교 parent=9(i:0) vs child=5(i:2) ===
[9]
----- -----
6 (5)
--- ---
8 7
배열 상태 (하향 비교)
i:0 i:1 i:2 i:3 i:4
9 6 5 8 7
^ •
선택 기준: 더 작은 자식 선택 (MinHeap)
규칙: parent > child → swap (Min)
판정: 교환 필요 (규칙 위반)
=== MinHeap POP: swap 실행 (i:0 ↔ i:2) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3 i:4
9 6 5 8 7
^ •
=== MinHeap POP: swap 후 위치 i:2 ===
5
----- -----
6 [9]
--- ---
8 7
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3 i:4
5 6 9 8 7
^
=== MinHeap POP 단계: 현재 루트 5 ===
[5]
----- -----
6 9
--- ---
8 7
배열 상태 (pop 전)
i:0 i:1 i:2 i:3 i:4
5 6 9 8 7
^
=== MinHeap POP: pop=5, 루트에 마지막 값 배치 ===
[7]
----- -----
6 9
---
8
배열 상태 (루트 교체 직후)
i:0 i:1 i:2 i:3
7 6 9 8
^
누적 pop 순서: 1 2 3 4 5
=== MinHeap POP: 하향 비교 parent=7(i:0) vs child=6(i:1) ===
[7]
----- -----
(6) 9
---
8
배열 상태 (하향 비교)
i:0 i:1 i:2 i:3
7 6 9 8
^ •
선택 기준: 더 작은 자식 선택 (MinHeap)
규칙: parent > child → swap (Min)
판정: 교환 필요 (규칙 위반)
=== MinHeap POP: swap 실행 (i:0 ↔ i:1) ===
배열 상태 (swap 직전)
i:0 i:1 i:2 i:3
7 6 9 8
^ •
=== MinHeap POP: swap 후 위치 i:1 ===
6
----- -----
[7] 9
---
8
배열 상태 (swap 직후)
i:0 i:1 i:2 i:3
6 7 9 8
^
=== MinHeap POP: 하향 비교 parent=7(i:1) vs child=8(i:3) ===
6
----- -----
[7] 9
---
(8)
배열 상태 (하향 비교)
i:0 i:1 i:2 i:3
6 7 9 8
^ •
선택 기준: 더 작은 자식 선택 (MinHeap)
규칙: parent > child → swap (Min)
판정: 교환 불필요 (규칙 만족)
=== MinHeap POP: 하향 종료 (규칙 만족) ===
6
----- -----
[7] 9
---
8
배열 상태 (하향 종료)
i:0 i:1 i:2 i:3
6 7 9 8
^
누적 pop 순서: 1 2 3 4 5
=== MinHeap POP 단계: 현재 루트 6 ===
[6]
----- -----
7 9
---
8
배열 상태 (pop 전)
i:0 i:1 i:2 i:3
6 7 9 8
^
=== MinHeap POP: pop=6, 루트에 마지막 값 배치 ===
[8]
--- ---
7 9
배열 상태 (루트 교체 직후)
i:0 i:1 i:2
8 7 9
^
누적 pop 순서: 1 2 3 4 5 6
=== MinHeap POP: 하향 비교 parent=8(i:0) vs child=7(i:1) ===
[8]
--- ---
(7) 9
배열 상태 (하향 비교)
i:0 i:1 i:2
8 7 9
^ •
선택 기준: 더 작은 자식 선택 (MinHeap)
규칙: parent > child → swap (Min)
판정: 교환 필요 (규칙 위반)
=== MinHeap POP: swap 실행 (i:0 ↔ i:1) ===
배열 상태 (swap 직전)
i:0 i:1 i:2
8 7 9
^ •
=== MinHeap POP: swap 후 위치 i:1 ===
7
--- ---
[8] 9
배열 상태 (swap 직후)
i:0 i:1 i:2
7 8 9
^
=== MinHeap POP 단계: 현재 루트 7 ===
[7]
--- ---
8 9
배열 상태 (pop 전)
i:0 i:1 i:2
7 8 9
^
=== MinHeap POP: pop=7, 루트에 마지막 값 배치 ===
[9]
---
8
배열 상태 (루트 교체 직후)
i:0 i:1
9 8
^
누적 pop 순서: 1 2 3 4 5 6 7
=== MinHeap POP: 하향 비교 parent=9(i:0) vs child=8(i:1) ===
[9]
---
(8)
배열 상태 (하향 비교)
i:0 i:1
9 8
^ •
선택 기준: 더 작은 자식 선택 (MinHeap)
규칙: parent > child → swap (Min)
판정: 교환 필요 (규칙 위반)
=== MinHeap POP: swap 실행 (i:0 ↔ i:1) ===
배열 상태 (swap 직전)
i:0 i:1
9 8
^ •
=== MinHeap POP: swap 후 위치 i:1 ===
8
---
[9]
배열 상태 (swap 직후)
i:0 i:1
8 9
^
=== MinHeap POP 단계: 현재 루트 8 ===
[8]
---
9
배열 상태 (pop 전)
i:0 i:1
8 9
^
=== MinHeap POP: pop=8, 루트에 마지막 값 배치 ===
[9]
배열 상태 (루트 교체 직후)
i:0
9
^
누적 pop 순서: 1 2 3 4 5 6 7 8
=== MinHeap POP 단계: 현재 루트 9 ===
[9]
배열 상태 (pop 전)
i:0
9
^
=== MinHeap POP: pop=9, 루트에 마지막 값 배치 ===
(empty)
배열 상태 (루트 교체 직후)
(empty)
누적 pop 순서: 1 2 3 4 5 6 7 8 9
최종 pop 순서: 1 2 3 4 5 6 7 8 9
****************************************************************************************************
'''
> Min Heap POP 과정이 모두 끝났다.
- 최종 POP 목록이 1에서 9까지 오름차순 정렬이 되었다.
- 초기 : [5, 3, 8, 1, 7, 9, 2, 6, 4] → [1, 3, 2, 4, 7, 9, 8, 6, 5] : Min Heap PUSH (상향 종료) → 최종 : [1, 2, 3, 4, 5, 6, 7, 8, 9] : Min Heap POP (하향 종료)
출력 결과는 여기까지 이다. 아래는 코드이다.
=====================================================
[Refs.]================================================
[코드] Max Heap과 Min Heap의 삽입(insert, 상향 단계), 삭제(delete, 하향 단계) 과정 구현
- 코드 앞부분은 트리의 구조와 노드 사이를 연결하는 모양을 출력하기 위한 내용이다. Heap 관련 코드 블럭은 메모되어서 구분할 수 있다.
- 참고로, 그 코드 앞부분 블럭은 이전 글의 주제인 트리(Tree)의 트리 구조를 그리는 데에도 동일하게 활용하였다.
#======================================================
# 트리(Tree) / 힙(Heap) 대시(—) 도식 + 표준 메시지(선택 기준/규칙/판정) + 애니메이션
# - 목표: 학습/시연용. 로직을 '보여주기'에 최적화된 설명형 구현.
# - 핵심 아이디어:
# (1) 트리는 레벨(BFS) 단위로 평면 좌표에 배치해 ASCII로 출력
# (2) 하이라이트: current=[X], visited=(X)로 표기
# (3) 힙은 배열 인덱스 ↔ 트리 포인터를 동기화해 시각화
# (4) '선택 기준/규칙/판정' 메시지로 학습 흐름을 문자로 안내
# ======================================================
import os, time
# ──────────────────────────────────────────────────────
# [공용 포인터 노드] : 출력/하이라이트에 사용
# - 값/왼자/오른자만 갖는 가벼운 구조. 학습용 시각화 포맷에 맞춤.
# - BST, Heap 배열을 모두 '포인터 트리'로 바꿔 출력할 때 재사용.
# ──────────────────────────────────────────────────────
class Node:
def __init__(self, value, left=None, right=None):
# value: 어떤 자료형도 가능(str/int 등). 출력 시 str()로 변환.
self.value, self.left, self.right = value, left, right
# ======================================================
# 대시(—) 도식 렌더러 (하이라이트 지원 + 괄호 잘림 방지 패치)
# - current 노드는 [X], 방문 노드는 (X) 로 출력(겹치면 current 우선)
# - 출력 폭 계산/넘침 보정/간격 유지가 핵심
# - spread: 레벨이 내려갈수록 좌우 확산 폭 축소 비율(0~1)
# - left_pad/right_pad: 괄호/대괄호 추가로 늘어난 폭을 안전하게 흡수
# ======================================================
def print_ascii_tree(root, current=None, visited=None,
cell=2, hpad=1, dash='-',
spread=0.65, left_pad=None, right_pad=None):
if not root:
print("(empty)")
return
# visited가 None이면 빈 set()으로. (가변 기본값 방지 패턴)
visited = visited or set()
# ── [1] 레벨 구성(BFS) : 부족한 자리는 None으로 채워 '완전 이진트리 형태'를 유지
# 이유: 좌표 계산(센터 확산)에 빈자리가 섞여도 인덱스가 어긋나지 않게 하기 위해.
levels, q = [], [root]
while any(q): # 현재 레벨에 실제 노드가 하나라도 있으면 진행
levels.append([n for n in q])
nq = []
for n in q:
if n: nq += [n.left, n.right]
else: nq += [None, None] # 빈 자리도 2칸 유지(다음 레벨 인덱스 보존)
q = nq
height = len(levels)
# ── [2] 텍스트 생성 규칙: 하이라이트 표기
# current=[X], visited=(X), 일반은 X
def text_of(n):
if not n: return ""
base = str(n.value)
# current가 visited에도 포함될 수 있으므로 current를 먼저 검사
if n is current: return f"[{base}]"
if n in visited: return f"({base})"
return base
# nodew: 노드 셀의 최소 폭(간격 보장) = max(cell, 표시 텍스트 최대 길이)
# - []/()등 장식 포함 길이를 반영해서 겹침 방지
nodew = max(cell, max(len(text_of(n)) for lvl in levels for n in lvl if n))
# base: 최하층 기준 폭 스케일(2^(h-1) * (nodew + hpad))
# - 깊이가 1 증가할 때마다 >> 1 (절반)로 줄여 확산폭 감소
base = (1 << (height - 1)) * (nodew + hpad)
# ── [3] 레벨별 센터 x좌표 계산
centers = []
for depth, lvl in enumerate(levels):
raw = (base >> depth) # 깊어질수록 간격 반감
off = max(nodew, int(raw * spread)) # spread로 확산을 '완만하게' 통제
if depth == 0:
centers.append([0]) # 루트는 x=0을 기준으로
else:
prev, curc = centers[-1], []
for p_x in prev:
# 부모 센터에서 좌/우로 off만큼 떨어진 지점에 자식 센터 배치
curc += [p_x - off, p_x + off]
centers.append(curc)
# ── [4] 전체 좌표 평행 이동 및 여백 설정
# - 괄호/대괄호로 인해 왼쪽이 잘리는 문제를 패딩으로 흡수
allx = [x for row in centers for x in row]
minx, maxx = min(allx), max(allx)
# 좌우 패딩 기본값: nodew+1. (문자 폭+여유 1칸)
LEFT_PAD = (nodew + 1) if left_pad is None else left_pad
RIGHT_PAD = (nodew + 1) if right_pad is None else right_pad
# shift: 전체를 오른쪽으로 민다(최소 x가 LEFT_PAD가 되도록)
shift = -minx + LEFT_PAD
# width: 좌/우 패딩 + 노드폭 고려 + 여유 2
width = (maxx - minx) + LEFT_PAD + RIGHT_PAD + nodew + 2
rows = height * 2 - 1 # 노드행과 대시행을 번갈아 배치
grid = [[" "] * width for _ in range(rows)]
# ── [5] 텍스트 그리기(중앙 정렬 + 좌/우 넘침 보정)
def put_text(r, cx, s):
# cx는 '센터 좌표', shift를 더해 그리드 좌표로 환산
start = int(cx + shift - len(s)//2)
# 좌측 넘침 시 앞부분 잘라내기(안전 출력)
if start < 0:
s = s[-start:]
start = 0
end = start + len(s)
# 우측 넘침 시 뒷부분 잘라내기
if end > width:
s = s[:width - start]
end = width
# 실제 그리드에 문자 배치
for i, ch in enumerate(s):
x = start + i
if 0 <= r < rows and 0 <= x < width:
grid[r][x] = ch
# ── [6] 부모-자식 사이 대시 연결
# '대시 블록 사이 1칸 공백'을 보장해 좌/우 연결선이 붙어보이지 않게 함.
def put_dash_between_centers(r, parent_cx, child_cx):
pc = int(parent_cx + shift) # 부모 기준 열
cc = int(child_cx + shift) # 자식 기준 열
if cc < pc:
# 왼쪽 자식: [cc, pc)까지 대시, pc는 공백(1칸)으로 남겨 간격 확보
for x in range(cc, pc):
grid[r][x] = dash
elif cc > pc:
# 오른쪽 자식: (pc, cc]까지 대시, pc는 공백(1칸)으로 남김
for x in range(pc+1, cc+1):
grid[r][x] = dash
# cc == pc는 비정상(같은 열) → 아무것도 하지 않음
# ── [7] 각 레벨 출력(노드행 + 대시행)
for d, lvl in enumerate(levels):
node_row = d * 2
# 노드 텍스트 출력
for i, n in enumerate(lvl):
if n: put_text(node_row, centers[d][i], text_of(n))
# 마지막 레벨이 아니면 연결 대시 출력
if d < height - 1:
dash_row = node_row + 1
for i, n in enumerate(lvl):
if not n: continue
p_x = centers[d][i]
li, ri = i*2, i*2+1
lc, rc = levels[d+1][li], levels[d+1][ri]
if lc: put_dash_between_centers(dash_row, p_x, centers[d+1][li])
if rc: put_dash_between_centers(dash_row, p_x, centers[d+1][ri])
# ── [8] 행 단위로 출력. 우측 공백은 rstrip()으로 제거해 화면 폭 최적화.
for r in range(rows):
line = "".join(grid[r]).rstrip()
if line: print(line)
# ======================================================
# Heap (배열) : Max/Min + 공용 유틸
# - 힙은 완전이진트리의 '배열 표현'을 사용
# - 부모/자식 인덱스 공식을 유틸로 제공(_p/_l/_r)
# ======================================================
class BaseHeap:
def __init__(self): self.a = [] # 내부 배열
def __len__(self): return len(self.a)
def _p(self, i): return (i - 1) // 2 # 부모 인덱스
def _l(self, i): return 2*i + 1 # 왼자식
def _r(self, i): return 2*i + 2 # 오른자식
def _swap(self, i, j): self.a[i], self.a[j] = self.a[j], self.a[i]
# 전형적인 최대 힙 구현
class MaxHeap(BaseHeap):
def push(self, x):
# 1) 배열 끝에 삽입
self.a.append(x); i = len(self.a) - 1
# 2) bubble-up: 부모보다 크면 교환(힙 불변식 복구)
while i > 0:
p = self._p(i)
if self.a[p] < self.a[i]: self._swap(p, i); i = p
else: break
def pop(self):
# 비어있으면 None
if not self.a: return None
# 1) 루트 꺼내기 + 마지막 원소를 루트로 이동
top, last = self.a[0], self.a.pop()
if self.a:
self.a[0] = last; i = 0
# 2) heapify-down: 더 큰 자식과 교환 반복
while True:
l, r, m = self._l(i), self._r(i), i
if l < len(self.a) and self.a[l] > self.a[m]: m = l
if r < len(self.a) and self.a[r] > self.a[m]: m = r
if m == i: break
self._swap(i, m); i = m
return top
# 전형적인 최소 힙 구현(부등호 반대)
class MinHeap(BaseHeap):
def push(self, x):
self.a.append(x); i = len(self.a) - 1
while i > 0:
p = self._p(i)
if self.a[p] > self.a[i]: self._swap(p, i); i = p
else: break
def pop(self):
if not self.a: return None
top, last = self.a[0], self.a.pop()
if self.a:
self.a[0] = last; i = 0
while True:
l, r, m = self._l(i), self._r(i), i
if l < len(self.a) and self.a[l] < self.a[m]: m = l
if r < len(self.a) and self.a[r] < self.a[m]: m = r
if m == i: break
self._swap(i, m); i = m
return top
# 배열 → 포인터 트리 + 노드 배열 반환(인덱스→노드 매핑)
# - 시각화를 위해 힙 배열을 즉시 포인터 트리로 구성
def heap_array_to_tree_with_nodes(a):
if not a: return None, []
nodes = [Node(v) for v in a]
for i in range(len(a)):
l, r = 2*i + 1, 2*i + 2
if l < len(a): nodes[i].left = nodes[l]
if r < len(a): nodes[i].right = nodes[r]
return nodes[0], nodes
# 힙 상태를 포인터 트리로 그리되, 현재/기타 인덱스를 하이라이트
def render_heap(a, current_idx=None, other_idxs=(), title=None):
root, nodes = heap_array_to_tree_with_nodes(a)
cur = nodes[current_idx] if (nodes and current_idx is not None and 0 <= current_idx < len(nodes)) else None
visited = {nodes[i] for i in other_idxs if 0 <= i < len(nodes)}
if title: print(title)
print_ascii_tree(root, current=cur, visited=visited)
# 배열 상태를 표처럼 정렬해 보여주는 보조 출력
# - 윗줄: 인덱스, 가운데: 값, 아랫줄: 포인터(^: current, •: other, ⟂: 겹침)
def print_array_table(a, current_idx=None, other_idx=None, note=None):
if note: print(note)
if not a:
print("(empty)\n"); return
n = len(a)
# 셀 폭: 값의 최대 문자열 길이에 여유(+2) 및 최소(3)
cellw = max(3, max(len(str(x)) for x in a)) + 2
def row(items): return " ".join(str(s).center(cellw) for s in items)
print(row([f"i:{i}" for i in range(n)]))
print(row(a))
ptr = []
for i in range(n):
if i == current_idx and i == other_idx: ptr.append("⟂")
elif i == current_idx: ptr.append("^")
elif i == other_idx: ptr.append("•")
else: ptr.append(" ")
print(row(ptr)); print()
# ======================================================
# 표준 메시지 포맷 애니메이션
# 1) Heap: push/pop
# 2) BST: insert/delete
# - 'clear_each_frame=True'일 때 매 프레임 콘솔 클리어로 애니메이션 느낌 제공
# - 선택 기준/규칙/판정 메시지로 개념을 글로도 동시에 설명
# ======================================================
class SimpleHeap:
# 시연 전용 경량 힙: is_max 플래그로 Max/Min 겸용
def __init__(self, is_max=True): self.a, self.is_max = [], is_max
def __len__(self): return len(self.a)
def _p(self, i): return (i - 1) // 2
def _l(self, i): return 2*i + 1
def _r(self, i): return 2*i + 2
# 상향/하향 비교 로직을 공통화
def _need_swap_up(self, parent, child):
# MaxHeap: parent < child → swap
# MinHeap: parent > child → swap
return (parent < child) if self.is_max else (parent > child)
def _preferred_child(self, i):
# 하향 시 비교할 '선호 자식' 선택
# - Max: 더 큰 자식, Min: 더 작은 자식
l, r, n = self._l(i), self._r(i), len(self.a)
if l >= n and r >= n: return None
if r >= n: return l
if l >= n: return r
return (l if self.a[l] >= self.a[r] else r) if self.is_max else (l if self.a[l] <= self.a[r] else r)
def animate_heap_pushes(heap: SimpleHeap, values, delay=0.8, clear_each_frame=True, name="Heap"):
# values의 각 값을 차례대로 push하면서
# - append 직후 상태
# - bubble-up 비교/스왑 전/후
# 를 시각/문자 동시 출력
for x in values:
# 1) append (맨 뒤에 삽입)
heap.a.append(x); i = len(heap.a) - 1
if clear_each_frame: os.system('cls' if os.name == 'nt' else 'clear')
render_heap(heap.a, current_idx=i, other_idxs=(), title=f"=== {name} PUSH: append {x} ===")
print_array_table(heap.a, current_idx=i, other_idx=None, note="배열 상태 (append 직후)")
print("선택 기준: 부모와 현재 노드 비교")
print("규칙:", "parent < child → swap (MaxHeap)" if heap.is_max else "parent > child → swap (MinHeap)")
print("설명:", "부모가 현재보다 작으면 상향 이동" if heap.is_max else "부모가 현재보다 크면 상향 이동")
time.sleep(delay)
# 2) bubble-up
while i > 0:
p = heap._p(i)
need = heap._need_swap_up(heap.a[p], heap.a[i])
if clear_each_frame: os.system('cls' if os.name == 'nt' else 'clear')
title = f"=== {name} PUSH: 비교 parent={heap.a[p]}(i:{p}) vs cur={heap.a[i]}(i:{i}) ==="
render_heap(heap.a, current_idx=i, other_idxs=(p,), title=title)
print_array_table(heap.a, current_idx=i, other_idx=p, note="배열 상태 (swap 전 비교)")
print("선택 기준: 부모와 현재 노드 비교")
print("규칙:", "parent < child → swap (MaxHeap)" if heap.is_max else "parent > child → swap (MinHeap)")
print("판정:", "교환 필요 (규칙 위반)" if need else "교환 불필요 (규칙 만족)")
time.sleep(delay)
if not need:
# 더 이상 위로 갈 필요가 없으면 종료
if clear_each_frame: os.system('cls' if os.name == 'nt' else 'clear')
render_heap(heap.a, current_idx=i, other_idxs=(p,), title=f"=== {name} PUSH: 상향 종료 (규칙 만족) ===")
print_array_table(heap.a, current_idx=i, other_idx=p, note="배열 상태 (상향 종료)")
time.sleep(delay * 0.6)
break
# 실제 교환
if clear_each_frame: os.system('cls' if os.name == 'nt' else 'clear')
print(f"=== {name} PUSH: swap 실행 (i:{p} ↔ i:{i}) ===")
print_array_table(heap.a, current_idx=i, other_idx=p, note="배열 상태 (swap 직전)")
heap.a[p], heap.a[i] = heap.a[i], heap.a[p]
render_heap(heap.a, current_idx=p, other_idxs=(), title=f"=== {name} PUSH: swap 후 위치 i:{p} ===")
print_array_table(heap.a, current_idx=p, other_idx=None, note="배열 상태 (swap 직후)")
i = p # 상향 이동된 위치에서 반복
time.sleep(delay)
def animate_heap_pops(heap: SimpleHeap, delay=0.9, clear_each_frame=True, name="Heap"):
# 힙이 빌 때까지 pop 반복
# - 루트 표시 → pop+루트교체 → 하향(heapify-down) 과정 시각/문자 출력
seq = []
while len(heap.a) > 0:
# 1) 현재 루트 표시
if clear_each_frame: os.system('cls' if os.name == 'nt' else 'clear')
render_heap(heap.a, current_idx=0, other_idxs=(), title=f"=== {name} POP 단계: 현재 루트 {heap.a[0]} ===")
print_array_table(heap.a, current_idx=0, other_idx=None, note="배열 상태 (pop 전)")
time.sleep(delay)
# 2) pop: 루트 반환 + 마지막 원소를 루트에 배치
top = heap.a[0]
last = heap.a.pop()
if heap.a:
self_last = last # 가독성용 별도 변수
heap.a[0] = self_last
seq.append(str(top))
if clear_each_frame: os.system('cls' if os.name == 'nt' else 'clear')
render_heap(heap.a, current_idx=0 if heap.a else None, other_idxs=(), title=f"=== {name} POP: pop={top}, 루트에 마지막 값 배치 ===")
print_array_table(heap.a, current_idx=0 if heap.a else None, other_idx=None, note="배열 상태 (루트 교체 직후)")
print("누적 pop 순서:", " ".join(seq))
time.sleep(delay)
# 3) heapify-down: 선호 자식과 비교하며 규칙 위반이면 교환
i = 0
while heap.a:
ch = heap._preferred_child(i)
if ch is None: break
need = heap._need_swap_up(heap.a[i], heap.a[ch])
prefer_text = "더 큰 자식 선택 (MaxHeap)" if heap.is_max else "더 작은 자식 선택 (MinHeap)"
rule_text = "parent < child → swap (Max)" if heap.is_max else "parent > child → swap (Min)"
if clear_each_frame: os.system('cls' if os.name == 'nt' else 'clear')
title = f"=== {name} POP: 하향 비교 parent={heap.a[i]}(i:{i}) vs child={heap.a[ch]}(i:{ch}) ==="
render_heap(heap.a, current_idx=i, other_idxs=(ch,), title=title)
print_array_table(heap.a, current_idx=i, other_idx=ch, note="배열 상태 (하향 비교)")
print("선택 기준:", prefer_text)
print("규칙:", rule_text)
print("판정:", "교환 필요 (규칙 위반)" if need else "교환 불필요 (규칙 만족)")
time.sleep(delay)
if not need:
# 더 내려갈 필요가 없으면 종료
if clear_each_frame: os.system('cls' if os.name == 'nt' else 'clear')
render_heap(heap.a, current_idx=i, other_idxs=(), title=f"=== {name} POP: 하향 종료 (규칙 만족) ===")
print_array_table(heap.a, current_idx=i, other_idx=None, note="배열 상태 (하향 종료)")
print("누적 pop 순서:", " ".join(seq))
time.sleep(delay * 0.6)
break
# 실제 교환
if clear_each_frame: os.system('cls' if os.name == 'nt' else 'clear')
print(f"=== {name} POP: swap 실행 (i:{i} ↔ i:{ch}) ===")
print_array_table(heap.a, current_idx=i, other_idx=ch, note="배열 상태 (swap 직전)")
heap.a[i], heap.a[ch] = heap.a[ch], heap.a[i]
i = ch
render_heap(heap.a, current_idx=i, other_idxs=(), title=f"=== {name} POP: swap 후 위치 i:{i} ===")
print_array_table(heap.a, current_idx=i, other_idx=None, note="배열 상태 (swap 직후)")
time.sleep(delay)
print("\n 최종 pop 순서:", " ".join(seq))
[코드 실행 - 출력 보기] Max Heap의 삽입과 삭제 코드를 출력하는 실행 코드
# --- Heap(Max/Min) 애니메이션(동일 포맷) ---
data = [5, 3, 8, 1, 7, 9, 2, 6, 4]
stars = 100
# ─────────────────────────────────────────────
# MaxHeap (부모 ≥ 자식 유지)
# ─────────────────────────────────────────────
print("\n=== MaxHeap 애니메이션 ===")
print("설명: MaxHeap은 부모 노드가 항상 자식보다 크거나 같은 값을 유지합니다.")
print(" 삽입 시 상향(bubble-up), 삭제 시 하향(heapify-down) 규칙을 적용합니다.")
print(" 비교 기준: parent < child → swap 실행 (큰 값이 위로 올라감)\n")
# 삽입 애니메이션
maxh = SimpleHeap(is_max=True)
print("설명: 아래 순서대로 삽입하며, 삽입 시마다 부모와 비교하여 상향 이동합니다.")
print(" 삽입 데이터:", data)
animate_heap_pushes(maxh, data, delay=0.4, clear_each_frame=False, name="MaxHeap")
print("\n" + '*' * stars + "\n")
# 삭제 애니메이션
print("설명: 이제 최대값(루트)을 하나씩 꺼내며 pop 연산을 시각화합니다.")
print(" 루트 제거 후 마지막 노드를 루트에 올리고, 자식과 비교하여 하향 교환합니다.\n")
animate_heap_pops(maxh, delay=0.5, clear_each_frame=False, name="MaxHeap")
print("\n" + '*' * stars + "\n")
[코드 실행 - 출력 보기] Min Heap의 삽입과 삭제 코드를 출력하는 실행 코드
# ─────────────────────────────────────────────
# MinHeap (부모 ≤ 자식 유지)
# ─────────────────────────────────────────────
print("\n=== MinHeap 애니메이션 ===")
print("설명: MinHeap은 부모 노드가 항상 자식보다 작거나 같은 값을 유지합니다.")
print(" 삽입 시 상향(bubble-up), 삭제 시 하향(heapify-down) 규칙을 적용합니다.")
print(" 비교 기준: parent > child → swap 실행 (작은 값이 위로 올라감)\n")
# 삽입 애니메이션
minh = SimpleHeap(is_max=False)
print("설명: 아래 순서대로 삽입하며, 삽입 시마다 부모와 비교하여 상향 이동합니다.")
print(" 삽입 데이터:", data)
animate_heap_pushes(minh, data, delay=0.4, clear_each_frame=False, name="MinHeap")
print("\n" + '*' * stars + "\n")
# 삭제 애니메이션
print("설명: 이제 최소값(루트)을 하나씩 꺼내며 pop 연산을 시각화합니다.")
print(" 루트 제거 후 마지막 노드를 루트에 올리고, 자식과 비교하여 하향 교환합니다.\n")
animate_heap_pops(minh, delay=0.5, clear_each_frame=False, name="MinHeap")
print("\n" + '*' * stars + "\n")
이전 자료 구조 트리(Tree)의 글에도 언급했듯이, 힙(Heap)에 관런한 이번 코드도 최대한 상세한 설명과 주석을 첨부하여 우선 이렇게 정리해두고자 한다. ChatGPT5를 적극적으로 활용하면서, 시행착오와 오류를 최대한 줄이자. 단, 맹종은 하지 말자! 우선 이해하는 것에 집중하고, 앞으로 필요한 출력만 가능하도록 코드 연습을 계속해보자.
즐거운 파이썬~ 즐 파이씽~~
[주의] 내용에 오류가 있을 수 있습니다.
'[Code] Study & Practice' 카테고리의 다른 글
| [HTML,CSS] tistroy, 제목 글자 크기 수정하기 (0) | 2025.11.09 |
|---|---|
| [Python] MySQL & Jupyter 연동 - 객체지향 프로그래밍(OOP)을 활용한 DB 작업 프로그램 예제 (0) | 2025.11.05 |
| [Python] 자료 구조4 - 이진 트리(Binary Tree)의 개념, 구조, 규칙 (0) | 2025.11.01 |
| [Python] 자료 구조3 - Hash table의 개념과 index 충돌 해결 방식 비교 (0) | 2025.10.30 |
| [Python] 자료 구조2 - Single & Double Linked List(연결 리스트)의 개념과 차이점 (1) | 2025.10.28 |