1. Deque(디큐, 덱)

DeQue : Double Ended Queue

▶ 스택과 큐의 결합체이다.
▶ 양쪽 끝에서 항목의 조회, 삽입, 삭제가 가능하다.

• 덱(Deque)은 어떤 쪽으로 입력하고 어떤 쪽으로 출력하느냐에 따라서 스택(Stack)으로 사용할 수도 있고, 큐(Queue)로도 사용할 수 있다.
  
  

✔️자바에서의 Deque 메소드

<삽입>

<삭제>

<조회>

2. 우선순위 큐(PriorityQueue)

▶ 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것 것을 말한다.
▶ 대표적인 예로는 최대값 추출이 있다.

• 큐에 [15423]이 있고 최대값을 구하는 우선순위 큐가 있을 때,
  [54321]로 추출된다.

▶ 우선순위 큐를 힙으로 구현한다고 가정할 떄, 힙의 경우 삭제나 삽입 과정에서 모두 부모와 자식 간의 비교만 계속 이루어진다.
▶ 삽입의 시간 복잡도가 배열이나 연결리스트에 비해 힙 기반이 월등하기 때문에, 편차가 심한 배열과 연결리스트보다는 힙으로 구현한다.

힙(Heap)

▶ 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조이다.
▶ 모든 노드에 저장된 값(우선순위)들은 자식 노드들의 것보다 (우선순위가) 크거나 같다.
▶ 결국 힙은 루트 노드에 우선순위가 높은 데이터를 위치시키는 자료구조이다.

최대 힙(Max Heap)은 완전 이진트리이면서, 루트 노드로 올라갈수록 저장된 값이 커지는 구조이다.

최소 힙(Min Heap)은 완전 이진트리이면서, 루트 노드로 올라갈수록 값이 작아지는 구조이다.

**최대 힙, 최소 힙 둘다 루트 노드에는 우선순위가 높은 것이 자리잡게 된다.

1) 삽입 연산
힙에 삽입을 하기 위해서는 힙 트리의 성질을 만족시키면서 새로운 요소를 추가해야 한다.

• 삽입 방법
  우선 완전이진트리의 마지막 노드에 이어서 새로운 노드를 추가한다.
  추가된 새로운 노드를 부모의 노드와 비교하여 교환한다.
  정상적인 힙트리가 될 때 까지 (더이상 부모노드와 교환할 필요가 없을 때까지) 반복한다.
  최악의 경우 새로 추가된 노드가 루트노트까지 비교하며 올라가야 하므로 시간복잡도가 O(log₂n)이다.

2) 삭제 연산
힙 트리에서 루트노드가 가장 우선순위가 높으므로 루트 노드를 삭제해야 한다.

• 삭제 방법
  루트 노드를 삭제한다.
  루트 노드가 삭제된 빈자리에 완전이진트리의 마지막 노드를 가져온다.
  루트 자리에 위치한 새로운 노드를 자식 노드와 비교하여 교환한다.
  이때 최대 힙인 경우 자식노드 중 더 큰 값과 교환을 하며, 최소 힙인 경우 더 작은 값과 교환을 한다.
  정상적인 힙트리가 될 때까지 반복한다.
  삭제 연산 또한 최악의 경우 루트노트부터 가장 아래까지 내려가야 하므로 시간복잡도가 O(log₂n)이다.

참고자료
1) https://chanhuiseok.github.io/posts/ds-4/
2) https://blog.naver.com/PostView.naver?blogId=ericalee97&logNo=222160947582&parentCategoryNo=&categoryNo=65&viewDate=&isShowPopularPosts=true&from=search