1. 힙(Heap)이란 무엇인가
1.1 힙(Heap)
힙(heap)은 완전 이진 트리(Complete Binary Tree) 구조를 가지면서, 힙 속성(heap property) 을 만족하는 자료구조이다.
※ 힙 속성이란?
예를 들어,
Min-heap 에서는 부모 노드의 값이 자식 노드의 값보다 작거나 같아야 한다. 반대로 Max-heap 은 부모 노드의 값이 자식 노드보다 크거나 같아야 한다.
Min heap과 Max heap에 대한 자세한 내용은 뒤에서 더 다뤄보고자 한다.
1.2 최대 힙(Max Heap) vs 최소 힙(Min Heap)
힙(Heap)은 크게 두가지, 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 나뉜다.
둘의 가장 큰 차이점은 부모 노드와 자식노드의 크기 관계이다.
| 구분 | 최대 힙 (Max Heap) | 최소 힙 (Min Heap) |
| 부모 - 자식 관계 | 부모 노드 ≥ 자식 노드 | 부모 노드 ≤ 자식 노드 |
| 루트(root) | 가장 큰 값 | 가장 작은 값 |
| 우선 순위 | 큰 값이 우선 | 작은 값이 우선 |
✅ 최대힙(Max Heap)
최대 힙(Max Heap)은 부모 노드의 값이 자식 노드의 값보다 크거나 같아야 하는(부모 노드 ≥ 자식 노드) 힙 구조 이다.
즉, 부모 노드는 항상 자식 노드보다 크거나 같은 값을 유지해야 한다.
그래서 가장 큰 값은 항상 루트(root) 노드에 위치한다.
⁉️ 형제 노드의 크기 관계
이 때, 왼쪽 자식이 오른쪽 자식보다 항상 커야 하나 하고 헷갈릴 수 있는데 그렇지 않다.
힙에서는 형제 노드(왼쪽 자식과 오른쪽 자식)끼리의 크기 관계는 중요하지 않다.
오직 부모 노드와 자식 노드 간의 대소 관계만 유지하면 된다.
✅ 최소 힙 (Min Heap)
최소 힙(Min Heap)은 부모 노드의 값이 자식 노드의 값보다 작거나 같아야 하는(부모 노드 ≤ 자식 노드) 힙 구조이다.
즉, 부모 노드는 항상 자식 노드보다 작은 값을 유지해야 한다.
그래서 가장 작은 값은 항상 루트(root)에 위치한다.
최대 힙과 마찬가지로, 최소 힙도 형제 노드끼리의 크기 관계는 중요하지 않다.
2. 힙의 특징 정리
2.1 부모 노드와 자식 노드의 관계
앞에서 최대 힙과 최소 힙의 특징을 살펴본 것처럼, 힙에서는 부모 노드와 자식 노드 간의 관계가 가장 중요하다.
삽입(insert)이나 삭제(delete)가 발생하면 이 관계가 깨질 수 있다.
이때, 힙은 부모와 자식 노드를 비교하며 다시 올바른 구조로 정렬하는 과정(heapify)을 거친다.
2.2 배열 기반으로 구현하는 이유
힙은 완전 이진 트리 구조를 따르기 때문에 배열 기반으로 구현하는 것이 좋다.
보통 트리 라고 하면,
left 나 right 처럼 노드를 연결해서 구현하는 방법을 먼저 떠올리게 될 것이다.
나도 처음에는 힙도 당연히 노드 기반으로 구현하는 줄 알았다.
하지만, 힙은 완전 이진 트리 구조를 가지기 때문에 오히려 배열 기반으로 구현하는 것이 더 효율적이다.
⁉️ 왜 배열이 더 잘 맞는가
직접 트리 구조를 배열로 바꿔보면서 왜 배열이 heap과 더 잘 맞는 지 한 번 아래의 예시를 통해 이해해보자.
만약 트리 구조가
10
/ \
20 30
/ \
40 50
위와 같은 구조이고 이 노드를 위에서부터 왼쪽 → 오른쪽 순서대로 배열에 넣어보면
[10, 20, 30, 40, 50]
와 같아진다.
이 구조를 배열로 표현하면 index와 value는 아래와 같다.
| index | 0 | 1 | 2 | 3 | 4 |
| value | 10 | 20 | 30 | 40 | 50 |
👉 이 때 우리는 규칙을 확인할 수 있다.
- index 0 의 왼쪽 자식 -> index1 (20)
- index 0 의 오른쪽 자식 -> index 2 (30)
- index 1의 왼쪽 자식 -> index 3 (40)
- index 1 의 오른쪽 자식 -> index 4 ( 50)
즉,
| 구분 | 의미 | 공식 |
| 왼쪽 자식 노드 | 현재 노드의 왼쪽 자식 위치 | 2i + 1 |
| 오른쪽 자식 노드 | 현재 노드의 오른쪽 자식 위치 | 2i + 2 |
| 부모 노드 | 현재 노드의 부모 위치 | (i - 1) // 2 |
이 공식을 따르게 된다.
👉 완전 이진 트리(힙)을 배열로 구현하는 것이 좋다.
2.3 일반 이진트리와의 차이점
그렇다면 힙이 완전 이진트리를 사용한다고 하는데, 완전 이진 트리가 아닌 일반 이진 트리를 이용한다면 어떻게 될까?
완전 이진 트리는 중간이 비지 않고 왼쪽부터 차곡차곡 채워지는 구조를 가진다.
즉, 일반 이진 트리보다 조금 더 규칙이 있는 트리라고 볼 수 있다.
만약 이진트리로 노드를 추가한다면, 아래와 같이 만들 수 있을 것이다.
10
/
20
\
50
이런 식으로 중간이 비면 배열로 저장할 수 있다.
[10, 20, ?, ?, 50]
👎 이런 식으로 빈칸이 생기면서 배열의 공간 낭비가 심하고, 인덱스 규칙도 깨지게 된다.
반면, 힙은 완전 이진 트리 구조를 유지하기 때문에 중간에 비는 일이 거의 없다.
그래서 배열로 저장해도 공간 낭비가 적고, 부모와 자식의 위치를 인덱스 계산만으로 쉽게 찾을 수 있다.
3. 힙의 동작 과정
3.1 삽입 (Insert)
Step 1. 새로운 요소를 힙의 가장 끝에 추가한다.
새로운 요소는 먼저 힙의 마지막 위치에 추가된다.
이는 완전 이진 트리 구조를 유지하기 위해서이다.
Step 2. 새로 추가된 요소가 힙 속성을 깨뜨릴 수 있다
새로운 요소가 추가되면, 부모 노드와의 대소 관계가 맞지 않아 힙 속성(heap property) 이 깨질 수 있다.
예를 들어 최대 힙(Max Heap)인데 자식 노드가 부모 노드보다 더 큰 값을 가진다면, 더 이상 힙 구조를 만족하지 못한다.
따라서 힙 속성을 다시 유지하기 위해 bottom-up 방식으로 heapify(재정렬) 를 수행한다.
즉, 새로 삽입된 노드에서 시작해 부모 노드와 비교하면서 위쪽(root 방향)으로 이동하며 올바른 위치를 찾아간다.
✔️ 예시로 한 번 이해해보기
말로만 보면 조금 헷갈릴 수 있어서, 최대 힙(Max Heap)에 새로운 값을 삽입하는 과정을 예시로 살펴보자.
예를 들어 아래와 같은 최대 힙(Max Heap)에 15를 삽입한다고 가정해보자.
위 과정을 보면,
- 먼저 새로운 값(15)을 힙의 가장 마지막 위치에 추가한다.
- 부모 노드와 값을 비교했을 때
15 > 3이므로 swap 한다. - 다시 부모 노드와 비교했을 때
15 > 10이므로 한 번 더 swap 한다. - 더 이상 부모 노드가 없으므로 삽입이 종료된다.
즉, 삽입은 새 노드가 올바른 위치를 찾을 때까지 부모 노드와 비교하며 위쪽으로 올라가는(bottom-up) 방식으로 진행된다.
3.2 삭제 (Delete)
힙에서의 삭제는 루트 노드(root)에서만 가능하다.
그런데 여기서 루트 노드를 그냥 삭제해버리면 완전 이진 트리 구조가 깨질 수 있기 때문에, 바로 삭제하지 않는다.
대신 힙의 구조를 유지하기 위해 아래와 같은 과정(Heapify)을 거친다.
Step1. 가장 마지막 노드를 루트 자리로 올린다.
먼저 힙의 가장 마지막 노드와 루트 노드의 위치를 바꾼다.
이렇게 하는 이유는 완전 이진 트리 구조를 유지하면서 삭제를 진행하기 위해서이다.
Step2. 기존 루트 노드를 삭제한다.
루트와 위치를 바꾼 뒤, 가장 마지막 노드 위치에 있던 기존 루트 노드를 삭제한다.
이 시점에서는 삭제는 끝났지만, 힙의 규칙이 깨졌을 가능성이 있다.
예를 들어 최대 힙(Max Heap)이라면, 루트 값이 자식 노드보다 작아질 수도 있기 때문이다.
따라서 힙 속성을 다시 맞추는 과정이 필요하다.
Step 3. 힙 규칙을 다시 맞춘다 (Heapify)
그래서 루트부터 시작해서 자식 노드와 값을 비교하면서 아래 방향으로 내려간다.
이때 힙 조건이 맞지 않으면 swap(교환) 하고, 다시 그 아래 자식 노드와 비교하는 과정을 반복한다.
✔️ 예시로 한 번 이해해보기
최대 힙에서 루트 값을 삭제하는 과정을 예시로 살펴보자.
예를 들어 아래와 같은 최대 힙에서 루트 값(10)을 삭제한다고 가정해보자.
위 과정을 순서대로 보면 다음과 같다.
- 먼저 가장 마지막 노드(4)를 루트 자리로 이동시킨다.
- 기존 루트 노드였던 10을 삭제한다.
- 이제 루트가 된 4는 힙 속성을 만족하지 않을 수 있기 때문에 자식 노드와 비교한다.
- 4 < 5 이므로 swap(교환) 한다.
- 그 아래 자식 노드와도 비교해야 하지만, 더 이상 힙 속성을 깨뜨리지 않으므로 정렬이 종료된다.
즉, 삭제는 루트를 제거한 뒤 힙 속성이 다시 맞춰질 때까지 위에서 아래 방향(top-down)으로 비교하며 내려가는 과정이라고 이해하면 된다.
4. Heap의 시간 복잡도
4.1 삽입(Insert)의 시간 복잡도
힙에서 원소를 추가할 때는 가장 마지막 위치(마지막 노드)에 새로운 값을 먼저 넣는다.
그 다음부터는 힙의 규칙을 유지하기 위해 부모 노드와 값을 비교하게 된다.
만약 현재 노드의 값이 부모 노드보다 더 우선순위가 높다면(예: 최대 힙에서 더 큰 값), 서로 swap(교환) 한다. (👉 Heapify)
즉,
마지막에 노드 삽입 → 부모와 비교 → 필요시 swap → 다시 부모와 비교 → … → 최대 루트까지 반복
이런 식으로 동작하게 된다.
또, 힙은 완전 이진 트리 구조이기 때문에, 원소 개수 N개에 대해 트리의 높이는 logN 이 된다.
따라서 삽입 과정에서 최대로 비교하는 횟수도 트리의 높이만큼 발생할 수 있으므로
👉 삽입의 시간 복잡도는 O(logN) 이 된다.
4.2 삭제(Delete)의 시간 복잡도
힙에서 루트 값을 삭제할 때는 조금 특별하게 동작한다.
루트를 그냥 삭제해버리면 힙 구조가 깨질 수 있기 때문에, 가장 마지막 노드를 루트 위치로 가져온 뒤 기존 루트를 삭제한다.
그 다음에는 새롭게 올라온 루트가 힙 조건을 만족하는지 확인해야 한다. (👉 Heapify)
그래서 자식 노드와 값을 비교하고, 필요하다면 swap 한다.이후에도 힙 조건이 맞지 않으면 아래 자식 노드와 또 비교하는 과정을 반복한다.
즉,
루트 삭제 → 마지막 노드를 루트로 이동 → 자식과 비교 → 필요 시 swap → 아래 자식과 다시 비교 → … → 최대 리프 노드까지 반복
이런 식으로 진행된다.
👉 삭제 역시 트리의 높이만큼만 비교가 이루어질 수 있기 때문에 시간 복잡도는 O(logN)이다.
4.3 탐색의 시간 복잡도
힙에서 특정 값을 찾는 시간 복잡도는 O(N) 이다.
“트리 구조니까 빠르지 않나?” 싶지만,
힙은 최댓값(또는 최솟값)을 빠르게 찾기 위해 만들어진 자료구조이지, 특정 값을 빠르게 탐색하기 위한 구조는 아니다.
Heap은 부모 노드와 자식 노드 사이에는 대소 관계가 정해져 있지만, 형제 노드끼리는 정렬 규칙이 없다.
그래서 이진 탐색 트리(BST)처럼
값 비교 → 왼쪽/오른쪽 중 한쪽만 선택 → 탐색 범위 절반씩 줄이기
이런 방식이 불가능하다.
따라서,
어떤 값을 찾는다고 할 때 원하는 값이 어디 있는 지 알 수 없기 때문에 최악의 경우 트리에 있는 모든 노드를 하나씩 확인해야 할 수도 있다.
👉 원소가 N개라면 최대 N번 탐색하게 될 수 있으므로 시간복잡도는 O(N)이다
5. 구현
내가 구현한 방식은 Heap이라는 부모 클래스를 먼저 만든 뒤, 공통적으로 사용하는 기능들을 먼저 정의하고,
이후 MaxHeap 과 MinHeap 클래스에서 비교 함수(compare_node)를 오버라이딩 하는 방식으로 구현해보았다.
1️⃣ Heap 클래스
Heap 클래스는 MaxHeap과 MinHeap에서 공통적으로 사용하는 기능들을 모아둔 부모 클래스이다.
예를 들어
- 부모 노드 인덱스 찾기
- 왼쪽 /오른쪽 자식 노드 인덱스 찾기
- swap
- insert /delete 함수
과 같은 기능은 최대 힙과 최소 힙 모두 거의 동일하게 사용된다.
따라서 중복 코드를 줄이기 위해 부모 클래스를 먼저 구현했다.
class Heap:
def __init__(self):
self.myHeap=[]
✅ 인덱스 계산 함수와 swap(), compare_node()
힙을 배열 기반으로 구현했기 때문에, 부모와 자식 노드의 위치는 인덱스 계산만으로 찾을 수 있다.
그래서 부모 노드, 왼쪽/오른쪽 노드의 인덱스를 반환하는 함수를 먼저 구현해보았다.
def get_parent_idx(self,index): # 부모 노드의 인덱스를 반환
return (index-1) //2
def get_left_idx(self,index): # 왼쪽 자식의 인덱스를 반환
return index* 2 +1
def get_right_idx(self,index): # 오른쪽 자식의 인덱스를 반환
return index *2 + 2
def swap_node(self,i,j): # self.heap의 i번째 인덱스의 값과 j번째 index의 값을 바꿔치기 한다
self.myHeap[j], self.myHeap[i] = self.myHeap[i], self.myHeap[j]
def compare_node(self, parent_val, child_val): # parent_val과 child_val를 비교한다
pass # -> MaxHeap 과 MinHeap에서 구체화한다. ✅ 노드 추가 함수
insert_node 함수는 새로운 값을 힙에 삽입하는 함수이다.
# ✅ 노드 추가 함수
def insert_node(self,data):
self.myHeap.append(data) # 일단 리스트의 맨 끝에 새로운 data를 추가한다
current_idx= len(self.myHeap) -1 # 현재 인덱스 (새로운 data의 인덱스)
# 힙의 구조에 맞게 인덱스 수정하기
## ⬇️ heapify
# 가장 끝에 새로운 데이터를 추가했기 때문에 그 노드를 기준으로 계속해서 올라가면서 (최대 root까지) 부모 노드와 자식 노드를 비교하면서 힙의 구조에 맞게 변형한다.
while current_idx > 0 : # 여기서 0 은 root노드의 인덱스를 의미함
parent_idx=self.get_parent_idx(current_idx)
parent_val= self.myHeap[parent_idx]
current_val=self.myHeap[current_idx]
if self.compare_node(parent_val,current_val):
break ## 부모- 자식 관계가 올바르면 while 문 멈춤
else :
self.swap_node(parent_idx,current_idx) # 부모 - 자식 관계가 올바르지 않으면, 부모 노드와 자식 노드 위치를 바꾼다
current_idx= parent_idx # 현재 index를 부모의 인덱스로 하면서 계속해서 위로 올라간다.
✅ 루트 노드 삭제 함수
힙에서는 루트 노드만 삭제할 수 있다.
def delete_node(self): # 루트 노드를 제거
if len(self.myHeap)==0 :
return None
# 데이터의 개수가 1일 때는 바로 pop()한다
elif len(self.myHeap)==1 : return self.myHeap.pop()
# ⬇️ 데이터의 개수가 2개 이상일 때
# 루트 노드의 값을 deleted_val 에 미리 저장해두기
deleted_val = self.myHeap[0]
self.myHeap[0]= self.myHeap.pop() # 힙의 맨 마지막 노드를 pop 해서 루트 자리로 덮어씌우기
## ⬇️ 루트에서부터 아래로 내려가면서 heapify 하기
# 지금 현재 root를 삭제하고 기존의 가장 뒤에 있던 것을 맨앞으로 두었기 때문에 여기서부터 다시 힙의 구조를 점검한다
current_idx = 0
while self.get_left_idx(current_idx) < len(self.myHeap): # 왼쪽 자식이 존재하는 동안 계속 아래로 내려가겠다
# (왼쪽 자식이 없으면 오른쪽 자식도 없음)- 완전 이진 트리의 특징
# == 자식 노드들 비교하기 ==
left_idx= self.get_left_idx(current_idx) # current_idx의 왼쪽
right_idx = self.get_right_idx(current_idx) # current_idx의 오른쪽
# 기본적으로 왼쪽 자식을 비교 대상(target_idx)으로 두자
target_idx = left_idx
if right_idx < len(self.myHeap) : # 오른쪽 자식이 존재하면
right_val=self.myHeap[right_idx] # 오른쪽 자식의 값
left_val= self.myHeap[left_idx] # 왼쪽 자식의 값
if self.compare_node(right_val, left_val): # 오른쪽 자식과 왼쪽 자식과 비교했을 때 오른쪽 자식이 힙 조건상 더 우선순위가 높다면
# 예) Max Heap : 오른쪽이 더 큼 / Min Heap : 오른쪽이 더 작음
target_idx = right_idx # target_idx가 right_idx가 된다
# 부모 노드와 대표 자식 (target _idx의 값)과 비교하기
target_val= self.myHeap[target_idx]
current_val=self.myHeap[current_idx]
if self.compare_node(current_val,target_val): # target vs 대표자식과 비교했을 때, current(부모)의 우선순위가 더 높으면
break # while 문을 빠져 나온다
self.swap_node(current_idx,target_idx) # False -> target의 우선 순위가 높으면 두 인덱스의 위치를 바꾼다
current_idx = target_idx # 위로 올라가기 위해 current_idx를 target_idx 로 바꾼다
return deleted_val # 기존 root노드를 반환한다.
### print_heap()
```python
def print_heap(self):
print(self.myHeap)
2️⃣ MaxHeap 클래스
MaxHeap 클래스에서는 부모 노드의 값이 자식 노드보다 커야 하기 때문에,
parent_val >= child_val
일 때, True를 반환하도록 구현하였다.
이미 부모 노드가 힙 조건을 만족한다면 swap할 필요가 없도록 만들어 보았다.
class MaxHeap(Heap):
def compare_node(self, parent_val, child_val):
# 부모가 자식보다 작으면 아래로 내려야 한다
# 부모가 자식보다 크거나 같으면 True / 부모가 자식보다 작으면 False return
return parent_val >= child_val
3️⃣ MinHeap 클래스
반대로 MinHeap 클래스에서는 부모 노드가 자식 노드보다 작아야 하기 때문에
parent_val <= child_val
을 기준으로 True를 반환하도록 구현하였다.
class MinHeap(Heap):
def compare_node(self,parent_val,child_val):
return parent_val <= child_val
▶️ 실행해보기
maxHeap= MaxHeap()
minHeap=MinHeap()
numbers=[ 30,40,10,20,50]
for num in numbers:
maxHeap.insert_node(num)
minHeap.insert_node(num)
print('max heap으로 했을 때 ->',end=' ')
maxHeap.print_heap()
print('min heap으로 했을 때 ->',end=' ')
minHeap.print_heap()
print('maxheap.delete()', maxHeap.delete_node())
maxHeap.print_heap()
실행 결과
전체 코드
class Heap:
def __init__(self):
self.myHeap=[]
def get_parent_idx(self,index): # 부모 노드의 인덱스를 반환
return (index-1) //2
def get_left_idx(self,index): # 왼쪽 자식의 인덱스를 반환
return index* 2 +1
def get_right_idx(self,index): # 오른쪽 자식의 인덱스를 반환
return index *2 + 2
def swap_node(self,i,j): # self.heap의 i번째 인덱스의 값과 j번째 index의 값을 바꿔치기 한다
self.myHeap[j], self.myHeap[i] = self.myHeap[i], self.myHeap[j]
def compare_node(self, parent_val, child_val): # parent_val과 child_val를 비교한다
pass # -> MaxHeap 과 MinHeap에서 구체화한다.
# ✅ 노드 추가 함수
def insert_node(self,data):
self.myHeap.append(data) # 일단 리스트의 맨 끝에 새로운 data를 추가한다
current_idx= len(self.myHeap) -1 # 현재 인덱스 (새로운 data의 인덱스)
# 힙의 구조에 맞게 인덱스 수정하기
## ⬇️ heapify
# 가장 끝에 새로운 데이터를 추가했기 때문에 그 노드를 기준으로 계속해서 올라가면서 (최대 root까지) 부모 노드와 자식 노드를 비교하면서 힙의 구조에 맞게 변형한다.
while current_idx > 0 : # 여기서 0 은 root노드의 인덱스를 의미함
parent_idx=self.get_parent_idx(current_idx)
parent_val= self.myHeap[parent_idx]
current_val=self.myHeap[current_idx]
if self.compare_node(parent_val,current_val):
break ## 부모- 자식 관계가 올바르면 while 문 멈춤
else :
self.swap_node(parent_idx,current_idx) # 부모 - 자식 관계가 올바르지 않으면, 부모 노드와 자식 노드 위치를 바꾼다
current_idx= parent_idx # 현재 index를 부모의 인덱스로 하면서 계속해서 위로 올라간다.
def delete_node(self): # 루트 노드를 제거
if len(self.myHeap)==0 :
return None
# 데이터의 개수가 1일 때는 바로 pop()한다
elif len(self.myHeap)==1 : return self.myHeap.pop()
# ⬇️ 데이터의 개수가 2개 이상일 때
# 루트 노드의 값을 deleted_val 에 미리 저장해두기
deleted_val = self.myHeap[0]
self.myHeap[0]= self.myHeap.pop() # 힙의 맨 마지막 노드를 pop 해서 루트 자리로 덮어씌우기
## ⬇️ 루트에서부터 아래로 내려가면서 heapify 하기
# 지금 현재 root를 삭제하고 기존의 가장 뒤에 있던 것을 맨앞으로 두었기 때문에 여기서부터 다시 힙의 구조를 점검한다
current_idx = 0
while self.get_left_idx(current_idx) < len(self.myHeap): # 왼쪽 자식이 존재하는 동안 계속 아래로 내려가겠다
# (왼쪽 자식이 없으면 오른쪽 자식도 없음)- 완전 이진 트리의 특징
# == 자식 노드들 비교하기 ==
left_idx= self.get_left_idx(current_idx) # current_idx의 왼쪽
right_idx = self.get_right_idx(current_idx) # current_idx의 오른쪽
# 기본적으로 왼쪽 자식을 비교 대상(target_idx)으로 두자
target_idx = left_idx
if right_idx < len(self.myHeap) : # 오른쪽 자식이 존재하면
right_val=self.myHeap[right_idx] # 오른쪽 자식의 값
left_val= self.myHeap[left_idx] # 왼쪽 자식의 값
if self.compare_node(right_val, left_val): # 오른쪽 자식과 왼쪽 자식과 비교했을 때 오른쪽 자식이 힙 조건상 더 우선순위가 높다면
# 예) Max Heap : 오른쪽이 더 큼 / Min Heap : 오른쪽이 더 작음
target_idx = right_idx # target_idx가 right_idx가 된다
# 부모 노드와 대표 자식 (target _idx의 값)과 비교하기
target_val= self.myHeap[target_idx]
current_val=self.myHeap[current_idx]
if self.compare_node(current_val,target_val): # target vs 대표자식과 비교했을 때, current(부모)의 우선순위가 더 높으면
break # while 문을 빠져 나온다
self.swap_node(current_idx,target_idx) # False -> target의 우선 순위가 높으면 두 인덱스의 위치를 바꾼다
current_idx = target_idx # 위로 올라가기 위해 current_idx를 target_idx 로 바꾼다
return deleted_val # 기존 root노드를 반환한다.
def print_heap(self):
print(self.myHeap)
## MaxHeap - Heap 을 상속받음
class MaxHeap(Heap):
def compare_node(self, parent_val, child_val):
# 부모가 자식보다 작으면 아래로 내려야 한다
# 부모가 자식보다 크거나 같으면 True / 부모가 자식보다 작으면 False return
return parent_val >= child_val
class MinHeap(Heap):
def compare_node(self,parent_val,child_val):
return parent_val <= child_val
maxHeap= MaxHeap()
minHeap=MinHeap()
numbers=[ 30,40,10,20,50]
for num in numbers:
maxHeap.insert_node(num)
minHeap.insert_node(num)
print('max heap으로 했을 때 ->',end=' ')
maxHeap.print_heap()
print('min heap으로 했을 때 ->',end=' ')
minHeap.print_heap()
print('maxheap.delete()', maxHeap.delete_node())
maxHeap.print_heap()
'python' 카테고리의 다른 글
| 재귀함수(Recursive Function) (0) | 2026.06.11 |
|---|---|
| 정렬 알고리즘 ① 버블정렬, 선택 정렬 , 삽입 정렬 (0) | 2026.06.10 |
| 시간 복잡도와 공간 복잡도 (0) | 2026.06.06 |
| 자료구조 - 해시 테이블 (Hash Table) (0) | 2026.06.04 |
| 자료구조 - 이중 연결 리스트(Doubly Linked List) (0) | 2026.06.03 |