05. 데크(deque) & 우선순위 큐(priority queue)

데크(deque)

• 스택과 큐의 결합체로 볼 수 있다.
• 양쪽 끝에서 항목의 조회, 삽입, 삭제가 가능하다.

우선순위 큐(Priority Queue)

• Queue와 비슷한 추상 데이터 타입이지만, 각 항목마다 연관된 우선순위가 있다.
• 두 항목의 우선순위가 같으면 큐의 순서를 따른다.
• 힙을 이용해 구현한다.

힙(Heap)

• 각 노드가 하위 노드보다 작은(또는 큰) 이진 트리이다.
• 균형 트리의 모양이 수정될 때, 다시 균형 트리로 만드는 시간복잡도는 O(log n)이다.
• 최대 최소값을 구하기 위해 만들어졌다.

  

최대힙(max heap) 구현하기

우선순위 큐 구현하기