일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- 배열
- Git
- 이진 탐색
- 탐색
- git hub
- type 함수
- 순차 탐색
- UNIX
- NQueen
- 스택
- 기초
- MiniHeap
- sys.stdin.readline()
- 그리디
- 문법
- 자료구조
- 동적 계획
- 정렬
- IT
- 우분투
- 알고리즘
- 분할 정복
- 트리
- 그래프
- 유닉스
- 자기개발
- 백준
- 파이썬
- format 메서드
- 재귀 함수
Archives
- Today
- Total
코딩고치
[파이썬][자료구조] 힙 (Heap) 본문
힙
- 힙은 데이터에서 최댓값과 최솟값을 빠르게 찾기 위한 완전 이진트리 (Complete Binary Tree)이다.
힙을 사용하는 이유
- 우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야 하는 알고리즘 구현에 사용된다.
- 이진트리의 경우 한번 연산이 진행되면 데이터가 1/2가 되므로 시간 복잡도가 O(logn)이 걸린다.
- 따라서 힙도 O(logn)이 걸린다 (배열의 경우 최악의 경우에 O(n)이 걸림).
힙의 구조
- 최댓값을 구하는 최대 힙 (Max Heap)과 최솟값을 구하는 최소 힙 (Min Heap)으로 구분된다.
- 최대 힙 : 각 노드의 값은 자식 노드의 값보다 크거나 같다 (가장 위가 가장 큰 값).
- 최소 힙 : 각 노드의 값은 자식 노드의 값보다 작거나 같다 (가장 위가 가장 작은 값).
- 데이터는 맨 위에 있는 Root Node를 가져온다. 이 때문에 시간이 적게 걸린다.
- 완전 이진트리의 형태를 갖는다.
- 데이터를 항상 왼쪽 노드부터 채워 나가는 구조
힙과 이진 탐색 트리의 차이점
- 힙은 각 노드의 값이 자식 노드보다 크거나 같다 (또는 작거나 같다).
- 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 오른쪽 자식 노드의 값이 가장 크다.
- 힙에서는 왼쪽 자식 노드와 오른쪽 자식 노드에 들어가는 데이터에 대해 이진 탐색 트리와 같은 조건이 따로 없다.
- 이진 탐색 트리는 전체 탐색을 빠르게 하기 위한 구조이며 힙은 최소/최댓값을 빠르게 구하기 위한 구조이다.
데이터 삽입
최대 힙에서 삽입 데이터가 힙의 데이터보다 클 경우
- 가장 아래 왼쪽부터 채운다.
- 현재 위치에서 부모 노드와 비교하여 위치를 바꿔준다.
- 부모 노드가 더 크거나 Root 노드까지 갈 때까지 위치를 바꿔준다.
- 최소 힙의 경우 최대 힙과 반대로 해주면 된다.
데이터 삭제하기
최대 힙
- 보통 삭제는 root 노드를 삭제하는 것이 일반적이다.
- 가장 마지막에 추가한 노드를 root 노드로 이동시킨다.
- root 노드의 자식 노드와 비교하여 작을 경우 자식 노드 중 큰 값과 위치를 바꾼다.
힙 구현
- 힙은 배열을 활용하여 구현한다.
- root 노드의 인덱스를 1로 지정하여 구현한다.
- 부모 노드 인덱스 = 자식 노드 인덱스 // 2
- 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2
- 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2 + 1
# 힙 클래스 구현
class Heap:
def __init__(self, num):
self.heap_list = list()
self.heap_list.append(None) # root node의 인덱스를 1로 하기 위함
self.heap_list.append(num)
heap = Heap(20)
heap.heap_list
[None, 20]
데이터 추가 기능 추가
# 힙 클래스 구현
class Heap:
def __init__(self, num):
self.heap_list = list()
self.heap_list.append(None) # root node의 인덱스를 1로 하기 위함
self.heap_list.append(num)
def switch(self, num_index):
if num_index == 1:
return False # root node 일때
parent_index = num_index // 2
if self.heap_list[num_index] > self.heap_list[parent_index]:
return True
return False
# 데이터 삽입
def insert(self, num):
if len(self.heap_list) == 0:
self.heap_array.append(None)
self.heap_list.append(num)
return True
self.heap_list.append(num)
#추가한 num이 부모 노드보다 크면 자리바꾸기 위한 코드
num_index = len(self.heap_list) - 1
while self.switch(num_index):
parent_index = num_index // 2
self.heap_list[num_index], self.heap_list[parent_index]\
= self.heap_list[parent_index], self.heap_list[num_index]
num_index = parent_index
return True
heap = Heap(20)
heap.insert(15)
heap.insert(10)
heap.insert(7)
heap.insert(5)
heap.insert(25)
heap.heap_list
[None, 25, 15, 20, 7, 5, 10]
데이터 삭제 기능 추가
# 힙 클래스 구현
class Heap:
def __init__(self, num):
self.heap_list = list()
self.heap_list.append(None) # root node의 인덱스를 1로 하기 위함
self.heap_list.append(num)
def switch(self, num_index):
if num_index == 1:
return False # root node 일때
parent_index = num_index // 2
if self.heap_list[num_index] > self.heap_list[parent_index]:
return True
return False
def switch_child(self, switch_index): # 자식 노드와 비교하여 작으면 자리 바꾸기 위함
left_child_index = switch_index * 2
right_child_index = switch_index * 2 + 1
# 왼쪽 차일드 노드가 없을 때
if left_child_index >= len(self.heap_list):
return False
# 왼쪽 차일드 노드만 있을 때
elif right_child_index >= len(self.heap_list):
if self.heap_list[switch_index] < self.heap_list[left_child_index]:
return True
else:
return False
#왼쪽 오른쪽 모두 있을 때
else:
if self.heap_list[left_child_index] > self.heap_list[right_child_index]:
if self.heap_list[switch_index] < self.heap_list[left_child_index]:
return True
else:
return False
else:
if self.heap_list[switch_index] < self.heap_list[right_child_index]:
return True
else:
return False
# 데이터 삽입
def insert(self, num):
if len(self.heap_list) == 0:
self.heap_array.append(None)
self.heap_list.append(num)
return True
self.heap_list.append(num)
#추가한 num이 부모 노드보다 크면 자리바꾸기 위한 코드
num_index = len(self.heap_list) - 1
while self.switch(num_index):
parent_index = num_index // 2
self.heap_list[num_index], self.heap_list[parent_index]\
= self.heap_list[parent_index], self.heap_list[num_index]
num_index = parent_index
return True
# 데이터 삭제
def delete(self):
if len(self.heap_list) <= 1:
return None
pop_num = self.heap_list[1] # root node 출력
self.heap_list[1] = self.heap_list[-1] # root node에 가장 마지막 데이터 바꿔 줌
del self.heap_list[-1]
switch_index = 1
while self.switch_child(switch_index):
left_child_index = switch_index * 2
right_child_index = switch_index * 2 + 1
# 왼쪽 차일드 노드만 있을 때
if right_child_index >= len(self.heap_list):
if self.heap_list[switch_index] < self.heap_list[left_child_index]:
self.heap_list[switch_index], self.heap_list[left_child_index]\
= self.heap_list[left_child_index], self.heap_list[switch_index]
switch_index = left_child_index
#왼쪽 오른쪽 모두 있을 때
else:
if self.heap_list[left_child_index] > self.heap_list[right_child_index]:
if self.heap_list[switch_index] < self.heap_list[left_child_index]:
self.heap_list[switch_index], self.heap_list[left_child_index]\
= self.heap_list[left_child_index], self.heap_list[switch_index]
switch_index = left_child_index
else:
if self.heap_list[switch_index] < self.heap_list[right_child_index]:
self.heap_list[switch_index], self.heap_list[right_child_index]\
= self.heap_list[right_child_index], self.heap_list[switch_index]
switch_index = right_child_index
return pop_num
heap = Heap(20)
heap.insert(15)
heap.insert(10)
heap.insert(7)
heap.insert(5)
heap.heap_list
[None, 20, 15, 10, 7, 5]
heap = Heap(20)
heap.insert(15)
heap.insert(10)
heap.insert(7)
heap.insert(5)
heap.insert(25)
heap.heap_list
[None, 25, 15, 20, 7, 5, 10]
heap.delete()
25
heap.heap_list
[None, 20, 15, 10, 7, 5]
힙의 시간 복잡도
- n개의 노드를 가진 힙에 데이터를 입력 또는 삭제 시 최악의 경우 트리의 높이만큼 비교해야 한다.
- h=log2n이므로 시간 복잡도는 O(logn)이다
'파이썬 > 자료구조' 카테고리의 다른 글
[파이썬][자료구조] 트리 (Tree) (0) | 2020.04.23 |
---|---|
[파이썬][자료구조] 해쉬 테이블(Hash Table) (1) | 2020.04.22 |
[파이썬][자료구조] 시간 복잡도 (0) | 2020.04.16 |
[파이썬][자료구조] 링크드 리스트 (Linked List) (0) | 2020.04.15 |
[파이썬][자료구조] 스택 (Stack) (0) | 2020.04.15 |