파이썬 힙(Heap)과 셋(Set)

힙(Heap), 셋(Set)

힙(Heap)

일반적인 큐(Queue)는 순서를 기준으로 가장 먼저 들어온 데이터가 가장 먼저 나가므로 FIFO(First-in First-out, 선입선출) 방식

순서가 아닌 다른 기준으로는?

우선순위 큐(Priority Queue)

우선순위(중요도, 크기 등 순서 이외의 기준)를 기준으로 가장 우선순위가 높은 데이터가 가장 먼저 나타나는 방식

• 가중치가 있는 데이터
• 작업 스케줄링
• 네트워크

우선순위 큐를 구현하는 방법

• 배열(Array)
• 연결 리스트
• 힙(Heap)

우선순위 큐 구현 별 시간 복잡도

힙(Heap)의 특징

최대값 또는 최소값을 빠르게 찾아내도록 만들어진 데이터 구조

완전 이진 트리의 형태로 느슨한 정렬 상태를 지속적으로 유지한다.

힙 트리에서는 중복 값을 허용한다

언제 사용해야할까?

• 데이터가 지속적으로 정렬되어야 하는 경우
• 데이터에 삽입/삭제가 빈번할때

파이썬의 heapq

Minheap(최소 힙)으로 구현되어 있음(가장 작은 값이 먼저 옴)

삽입, 삭제, 수정, 조회 연산의 속도가 리스트보다 빠르다.

1) heapq.heapify() 2) heapq.heappop(heap) 3) heapq.heappush(heap, item)

https://www.daleseo.com/python-heapq/

셋(set)

셋은 수학에서의 ‘집합’을 나타내는 데이터 구조로 python에서는 기본적으로 제공되는 데이터 구조다.

셋의 연산

1. .add() O(1)
2. .remove() O(1)
3. +(합) O(N)
4. -(차) O(N)
5. &(교) O(N)
6. ^(대칭차집합) O(N)

셋은 언제 사용해야할까?

1. 데이터의 중복이 없어야 할때(고유값들로 이뤄진 데이터가 필요할때)
2. 정수가 아닌 데이터의 삽입/삭제/탐색이 번번히 필요할때