힙(heap)

---

힙은 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 완전이진트리란 마지막을 제외한 모든 노드에서 자식들이 꽉 채워진 이진트리를 말한다.

우선순위 큐란 우선순위의 개념을 큐에 도입한 자료구조로 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 추출되는 구조이다.

우선순위 큐 활용

• 시뮬레이션 시스템
• 네트워크 트래픽 제어
• 운영 체제에서의 작업 스케쥴링
• 수치 해석적인 계산

힙의 종류

---

최대힙

부모 노드의 값이 자식 노드들의 값보다 항상 크다

최소힙

부모 노드의 값이 자식 노드들의 값보다 항상 작다

힙을 저장하는 표준적인 자료구조는 배열이다.

힙에서의 부모노드와 자식노드의 관계

• 왼쪽 자식의 인덱스 = 부모의 인덱스 * 2
• 오른쪽 자식의 인덱스 = 부모의 인덱스 *2 + 1
• 부모의 인덱스 = 자식의 인덱스 / 2

힙의 삽입과 삭제

---

삽입

새로운 요소가 들어오면 마지막 노드에 이어서 삽입하고 부모 노드들과 교환해서 힙의 성질을 만족하면 반복한다.

삭제

루트 노드가 삭제되면 삭제된 루트노드에 힙의 마지막 노드를 가져온 후 힙을 재구성한다.

파이썬 힙 라이브러리

---

최댓값과 최솟값을 찾는 연산을 빠르게 할 때 heapq 모듈을 사용한다.

heapq는 기본적으로 최소힙을 다루기 때문에 최대힙은 튜플은 사용한 다른 요령이 필요하다.

import heapq

heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)

result = heapq.heappop(heap)

print(result)

10

만약 이미 리스트가 생성되어 있는 경우라면 heapfipy를 통해 힙 자료형으로 변환할 수 있다.

heap2 = [50 ,10, 20]
heapq.heapify(heap2)

print(heap2)

[10, 50, 20]