비선형 자료구조 - 우선순위 큐, 딕셔너리, 집합

1. Priority queue

파이썬은 min-heap이다. root-node에 최소값이 위치한다는 뜻.

삽입/삭제 시간복잡도는 logN이다.

 

heapq 모듈은 thread-safe한 모듈은 아니지만 빠르다.

import heapq

pq = []
heapq.heappush(pq, 6)
heapq.heappush(pq, 10)
heapq.heappush(pq, -7)
heapq.heappush(pq, 15)
heapq.heappush(pq, -4)
heapq.heappush(pq, 0)
print(pq)
while pq:
    heapq.heappop(pq)
    print(pq)

보면 최상단에 최소값이 위치할 뿐 나머지는 정렬이 되어있지 않다.

 

2. Dictionary 

key, value의 쌍을 이루는 구조.

다른 언어에서는 Map 구조라고 부름.

파이썬은 hash 구조여서 삽입/삭제의 시간복잡도는 O(1)

m = {}
m["a"] = 10
m["b"] = 500
m["c"] = -10
print("size: ", len(m))
for k in m:
    print(k, m[k])

3. Set

중복이 허용되지 않음.

삽입/삭제의 시간복잡도는 O(1)

s = set()
s.add(123)
s.add(2)
s.add(4576)
s.add(2)
s.add(1234)
s.add(405)
print("size: ", len(s))
print(s)
for i in s:
    print(i)