우선순위 큐과 힙

우선순위 큐

큐가 FIFO(First In, First Out)구조인 것을 안다.
우선순위 큐는 들어가는 순서와 관계없이 우선순위가 높은 데이터를 먼저 출력한다.
우선순위 큐는 힙 자료구조를 이용해서 구현한다.

힙(Heap)

• 힙(Heap)은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조이다.
• 이진탐색트리(BST)와 달리 중복된 값이 허용된다.
• 힙 종류

  최대힙 -> 부모노드 ≥ 자식노드
  
  최소힙 -> 부모노드 ≤ 자식노드
  

빅오 표기법으로 나타낸 시간 복잡도

최대힙, 최소힙, 절댓값힙 문제 적용

참고 https://aerocode.net/193
참고 https://suyeon96.tistory.com/31