[자료구조] 힙
📣 힙(Heap) 이란?
힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조로서 다음과 같은 힙 속성을 만족한다.
📌 부모와 자식노드간의 대소 관계 존재
예를 들어, A가 B의 부모노드일 경우, A의 key값과 B의 key값 사이에는 대소관계가 성립한다. 키값의 대소관계는 오직 부모자식노드 간에만 발생, 형제노드끼리는 상관이 없다. -> 이진탐색트리와의 차이점이라고 볼 수 있다.
📌 최대힙 그리고 최소힙
힙은 딱 2가지의 종류로 나뉘어지는데 부모노드의 키값이 자식노드의 키값보다 항상 큰 '최대힙', 그리고 부모노드의 키값이 자식노드의 키값보다 항상 작은 '최소힙'이 있다.
📌 우선순위 최상위 or 최하위 노드 -> 뿌리노드
힙에서는 가장 높은(혹은 가장 낮은) 우선 순위를 가지는 노드가 항상 root노드에 오게 되는 특징이 있다. 이를 응용하면 자동으로 최소힙을 구현하는 python의 내장 모듈 heapq에서도 최대힙을 구현해낼 수 있다.
🔍 정의와 특성에 따라 힙 찾기!
5
3 4
1 2 ❌ 완전이진트리가 아니라 힙이 아니다.
------------------------------------------------
5
3 1
2 4 ❌ 자식노드가 부모노드보다 커서 힙이 아니다.
👊 최대힙 자료구조 직접 구현해보기
class BinaryMaxHeap:
def __init__(self):
# None으로 시작하는 하나의 배열을 만든다.
self.items = [None]
def __len__(self):
# magic function
# index 1부터 시작하니 기본 len 함수보다 1 작다.
return len(self.items) - 1
def _percolate_up(self):
# 가장 위에 도달할 때까지 부모요소와 크기를 비교합니다.
# 부모요소보다 클 때까지 반복합니다.
cur = len(self)
parent = cur // 2
# value 값을 바꿔주는 부분
while parent > 0:
if self.items[cur] > self.items[parent]:
self.items[cur], self.items[parent] = self.items[parent], self.items[cur]
# index 값을 바꿔주는 부분
cur = parent
parent = cur // 2
def _percolate_down(self, cur):
# 자식노드가 더 클 경우, 부모노드와 자리를 바꿉니다.
biggest = cur
left = 2 * cur
right = 2 * cur + 1
# if 문 두개로 자식노드 중 더 큰 키값을 가진 노드와 자리를 바꾸게 됩니다.
if left <= len(self) and self.items[left] > self.items[biggest]:
biggest = left
if right <= len(self) and self.items[right] > self.items[biggest]:
biggest = right
# 만일 여기서 biggest와 cur이 같다면 부모노드가 자식노드보다 크다는 것.
# 더이상 down 할 필요가 없음
if biggest != cur:
self.items[cur], self.items[biggest] = self.items[biggest], self.items[cur]
self._percolate_down(biggest)
def insert(self, k):
# 배열의 마지막에 요소를 추가한 다음에 percolate_up을 계속해서 실시합니다.
self.items.append(k)
self._percolate_up()
def extract(self):
# 루트 노드와 제일 마지막 노드를 바꾸고 가장 마지막 요소를 제거합니다.
# 인덱스 1에서부터 아래로 계속해서 내려갑니다.
# 원래 root 노드였던 것을 반환합니다.
if len(self) < 1:
return None
root = self.items[1]
self.items[1] = self.items[-1]
self.items.pop()
self._percolate_down(1)
return root
📘 메모할 내용
- 시작할 때 self.items에 None값을 넣고 시작하는 이유는 heap의 index를 1부터 시작하기 위함이다. 이렇게 해야 아래로 내려갈 때 left index를 2 parent, right index를 2 parent + 1로 해줄 수 있다.
Author And Source
이 문제에 관하여([자료구조] 힙), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mindfulness_22/자료구조-힙저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)