[이론] 힙 Heap, 셋 Set

힙 Heap 이란?

큐와 다르게 순서를 기준으로 데이터를 나열하는 것이 아닌, 

다른 기준으로 데이터를 나열한다. 

 

heap이 필요한 경우

우선순위 큐는 우선순위(중요도, 크기 등 순서 이외의 기준)를 기준으로

가장 우선순위가 높은 데이터가 가장 먼저 나가는 방식이다.

 

 

우선순위를 기준으로 가져올 요소를 결정(dequeue) 하는 큐

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

우선순위 큐(Priority Queue) 를 구현하는 방법

1. 배열 array O(1)
2. 연결 리스트 Linked List O(1)
3. 힙 Heap O(logN)

 

힙 특징

• 최대/최소값을 빠르게 찾도록 만들어진 데이터 구조이다. 
• 그러므로 느슨한 정렬 상태를 지속적으로 유지한다.
• 힙 트리에서 중복 값을 허용한다.

 

힙 활용

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

파이썬의 heapq 모듈

• Minheap(최소 힙)으로 구현되어 있다 (가장 작은 값이 맨 앞으로 정렬된다)
• 삽입, 삭제, 수정, 조회 연산의 속도가 리스트보다 빠르다.
• 리스트이지만, 알아서 느슨한 정렬 상태를 유지한다.
• 그래서 값을 빠르게 뽑아낼 수 있다.

import heapq

numbers = [5, 3, 2, 4, 1]

heapq.heapify(numbers)  # 변수에 저장하여 바꾸는 것이 아닌 numbers가 바뀐다. 
print(numbers)
# >>> [1, 3, 2, 4, 5] -> 최솟값과 최댓값만 고려하여 느슨한 정렬 상태를 만들었다.
# heapify는 원본을 바꾼다. 

result = heapq.heapify(numbers)
print(numbers)
# 만약 heapq를 result 변수에 저장한다면 result는 none이다. 


heapq.heappop(numbers)
print(numbers)
# >>> [2, 3, 5, 4] -> 1이 빠지면서 최솟값이 된 2가 앞으로 나왔다. 

heapq.heappush(numbers, 10)
heapq.heappush(numbers, 0)
print(numbers)
# >>> [0, 2, 3, 5, 10, 4] -> 0은 맨 앞, 10은 어중간하게 들어간다.

heapq를 불러와 사용한다. 

heapq.heapify / heappush / heappop 을 사용하여 데이터 삽입 및 제거를 한다. 

 

 

셋 Set

'집합'을 나타내는 데이터 구조로 기본적으로 제공되는 데이터 구조이다.

 

셋의 연산

• .add()
• .remove()
• |  (합집합)
• - (차집합)
• & (교집합)
• ^ (대칭차)

 

셋 활용

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