[파이썬 알고리즘 인터뷰] 데크, 우선순위 큐

- 데크 (double-ended queue): 양 쪽에서 삽입 및 삭제 가능

- ADT는 이중연결리스트로 구현

 

641. design circular deque

- 이중 연결 리스트로 구현(빈 head, tail)

* 배열은 첫 인덱스에 삽입 시 O(n)

 

- 우선순위 큐: 특정 조건에 따른 우선순위가 가장 높은 순으로 추출 (ex. 최댓값 추출) -> 정렬 알고리즘으로 구현 가능

- 다익스트라 알고리즘이나 힙 자료구조와 관련이 깊음

 

23. merge k sorted lists

- 파이썬 heapq 모듈 (최소 힙): 이진 트리 기반

1. 원소들이 정렬된 상태(키 기준)로 삽입, 삭제

2. 가장 작은 원소가 첫 인덱스에 위치

3. 모든 원소들은 자식 원소들보다 작거나 같게 위치

* 두번째로 작은 값 확인하려면 가장 작은 값 삭제하고 첫 인덱스 확인

* 중복값 푸쉬 불가능