최소힙

힙

• 완전 이진 트리의 일종으로 우선순위 큐를 구현하기위해 사용하는 자료구조
• 여러개의 값들 중 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
• 힙은 일종의 반정렬 상태(느슨한 정렬상태)를 유지한다.

최대힙

• 부모노드의 키값이 자식 노드의 키값보다 크거나 같은 완전 이진 트리

최소힙

• 부모 노드의 키 값이 자식 노드의 키값보다 작거나 같은 완전 이진 트리
  

최소힙에 데이터를 삽입하는 방법

1. 완전이진트리의 요건을 만족시키기위해 삽입
2. 자신의 값과 부모노드값을 비교해 자신의 값이 더 작으면 자리를 바꿈
3. 자신의 값이 부모노드값보다 작을때까지 혹은 루트에 도착할때까지 반복

• 이 작업은 한 레벨씩 루트까지 올라간다면 한번 돌때마다 절반씩 떨어져 O(log(n))의 시간 복잡도를 가진다.

최소힙에서 최솟값 꺼내기

1. 최소값을 당연히 루트에 있으므로 1을 가져온다.
2. 루트 자리가 비어버렸으니 채워야해 완전 이진 트리의 맨 마지막 노드를 가져온다.
3. 가져오면 정렬이 안되어있는 상태이므로 자신의 자식노드와 비교해서 자기보다 작은 노등

완전 이진트리

• 중간 노드가 비어있지않고 빽빽하게 이루어진 트리
  

---

파이썬 힙 자료구조

• 파이썬 heapq모듈은 heapq 알고리즘을 제공한다.
• 모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리 구조인데, 내부적으로는 인덱스 0 에서 시작해 k번째 원소가 항상 자식 원소들 (2k+1, 2k)보다 작거나 같은 최소 힙의 형태로 정렬된다.

힙 함수 활용하기

• heapq.heappush(heap, item) : item를 heap에 추가
• heapq.headpop(head) : heap에서 가장 작은 원소를 pop & 리턴 비어있는 경우 indexError
• heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환

힙 생성 & 원소 추가

heapq 모듈은 리스트를 최소 힙처럼 다룰 수 있도록 하기때문에 빈 리스트를 생성하고 heapq의 함수를 호출할때마다 리스트를 인자에 넘겨야한다.

import heapq

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

print(heap)

생성해둔 리스트가 있을시 heapify 함수를 통해 힙 자료형으로 변환

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

print(heap2)

힙에서 원소 삭제 - 가장 작은 원소를 힙에서 제거, 그의 결과값을 리턴