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

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

• 데크(Deque, Double-Ended Queue)
  • 양쪽 끝을 모두 추출할 수 있는 큐 형태의 추상 자료형
  • 양쪽에서 삽입/삭제 모두 가능
  • 스택과 큐의 특징을 모두 가짐
  • 배열 / 연결 리스트 모두 구현 가능하지만, 이중 연결 리스트 구현이 어울림
• 우선순위 큐
  • 큐 / 스택 같은 추상 자료형과 유사하나 요소의 우선순위와 연관
  • 특정 조건에 따라 우선순위가 가장 높은 요소가 추출되는 자료형
    - ex) 최댓값 추출
  • 정렬 알고리즘을 사용하면 우선순위 큐를 만들 수 있음
  • 시간
    1. 정렬에 대한 시간
       - S(n) = O(n log n)
    2. 새 요소의 삽입/삭제 시간
       - O(S(n))
    3. 최대값을 가져오는데 걸리는 시간
       - O(1)
  • 그러나 실제로는 힙 정렬 등의 더 효율적인 방법을 활용
  • 다익스트라 알고리즘 등 다양한 분야에서 활용
  • Heap 자료구조와도 관련이 깊음