[22.08.02] Heap & Set

Heap & Set

#heap #set #heapq

1. Heap

   • 우선순위 큐

     순서가 아닌 우선순위를 기준으로 가져올 요소를 결정하는 큐

     1. 가중치가 있는 데이터
     2. 작업 스케줄링
     3. 네트워크

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

     1. 배열
     2. 연결 리스트
     3. 힙

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

     연산 종류	Enqueue	Dequeue
     배열	O(1)	O(N)
     정렬된 배열	O(N)	O(1)
     연결리스트	O(1)	O(N)
     정렬된 연결리스트	O(N)	O(1)
     힙	O(logN)	O(logN)

   • 힙(Heap)의 특징

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

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

   • 힙은 언제 사용해야할까?

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

   • 파이썬의 heapq 모듈

     Minheap으로 구현되어 있음. 가장 작은 값이 먼저 옴

     CRUD 연산의 속도가 리스트보다 빠르다.

   • 힙과 리스트 비교

     연산 종류	힙	리스트
     Get Item	O(1)	O(1)
     Insert Item	O(logN)	O(1) 또는 O(N)
     Delete Item	O(logN)	O(1) 또는 O(N)
     Search Item	O(N)	O(N)

   • 큐와 힘의 사용법 비교

     # Queue
             dequeue <= ㅁㅁㅁㅁ <= enqueue    
     # <- 가장 오래된 데이터 <- 가장 최신 데이터 <-
          
     # Heap
     heapq.heappop() <= ㅁㅁㅁㅁ <= heapq.heappush()
     # <- 가장 작은 데이터 <- 가장 큰 데이터 <-
     

   • 딕셔너리 메서드

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

2. Set

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

   • 셋의 연산

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

   • 셋은 언제 사용해야 할까?

     1. 데이터의 중복이 없어야 할 때
     2. 정수가 아닌 데이터의 삽입/삭제/탐색이 빈번히 필요할때

   • 셋 연산의 시간 복잡도

     연산 종류	시간복잡도
     탐색	O(1)
     제거	O(1)
     합집합	O(N)
     교집합	O(N)
     차집합	O(N)
     대칭 차집합	O(N)