[자료구조] 힙(heap)/ 최대힙(Max-Heap) / 최소힙(Min-Heap) / 자료구조 힙 / 힙정렬

✔ 힙(heap)

힙이란? 1등을 찾기 위한 자료구조이다.  최소힙, 최대힙으로 최댓값과 최솟값을 빠르게 찾아낼 수 있다.

 완전 이진 트리의 일종으로, 루트 노드에 있는 원소(1등 원소)를 뽑으면, 2등이 자동으로 1등이 된다.

---

📝 힙의 성질

• 완전 이진트리(모든 노드의 자식이 두개)의 일종으로, 리프 노드(제일 마지막 노드)를 제외한 자식 노드는 반드시 2개이다.
• 완전 이진트리는 중복을 허용하지 않지만, 자료구조 힙은 중복을 허용한다.
• 부모는 자식 보다 반드시 크거나(Max-Heap), 부모는 자식 보다 반드시 작다.(Min-Heap)
• 트리를 배열로 표현할 수 있다.

---

위의 설명에 따르면, 결론적으로 자료구조 힙은 루트 원소(제일 큰 값 or 제일 작은 값)를 제거하면서 원하는 값(제일 큰 값 or 제일 작은 값)을 찾는 것이다.

 

💻 최소힙(Min-Heap) 구현

import sys
import heapq

n = int(sys.stdin.readline())
H = []
# 자연수라면 in heap 0이라면 출력 + out heap

for _ in range(n):
    x = int(sys.stdin.readline())

    if x!=0:
        heapq.heappush(H, x) # H에 x push
        
    elif x == 0 and len(H) != 0:
        print(heapq.heappop(H))
        
    else:
        print(0)

파이썬의 heapq 모듈을 사용하여, 최소힙을 구현하였다.

 

+ 파이썬 heapq 모듈 설명 추가

+ 최대힙 구현 추가

+ 모듈 없이 구현 추가