Heap

힙이란?

• 여러 개의 값들 중에서 최대값이나 최소값을 빠르게 찾아내도록 만들어진 자료구조
• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
• 힙 트리에서는 중복된 값을 허용

< heap 삽입 >

1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입
2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질 만족

< heap 삭제 >

1. 최대 힙에서 최대값은 root node이므로 rote note가 삭제
2. 삭제된 root node에는 heap의 마지막 node를 가져옴
3. heap을 재구성

deque, heapq 차이 및 사용법

• heapq 모듈은 최소 heap을 지원하는 모듈로 직접 최소 힙을 구현하지 않아도 되는 장점이 있음.

deque

• 선입선출
• BFS

from collections import deque
q = deque()
q.append('l')
q.popleft()

heapq

• 최소힙, 최대힙
• 최소값이나 최대값을 빨리 찾아야 할 때

from heapq import heappush, heappop, heapify
q=[]
heappush(q,1)

• 힙 상태를 유지하며, 데이터 삽입
  heappop(q)

1. 가장 작은 원소를 빼냄
2. 나머지 원소가 힙을 유지하도록 정렬
   heapify(arr)

• 주어진 리스트를 heap 정렬할 때 사용 (ex- heapq.heapify(list))