우선순위 큐 구현 방식, 삽입 시간, 삭제 시간, 힙 정렬

 

이것이 코딩테스트다. 나동빈 신님의 강의를 바탕으로 작성하였습니다.

---

 우선순위 큐

  '우선순위가 가장 높은 데이터를 가장 먼저 삭제'하는 자료구조.
 예를 들어 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내 확인하는
 경우에 우선순위 큐를 이용할 수 있다.
 Python, C++, JAVA를 포함한 대부분의 프로그래밍 언어에서 '표준 라이브러리 형태로 지원'함.

 

 자료구조 : 추출 데이터
 스택 : 가장 나중에 삽입된 데이터
 큐 : 가장 먼저 삽입된 데이터
 우선순위 큐 : 가장 우선 순위가 높은 데이터

 

 

힙(Heap)

'우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나'. 
 최소 힙과 최대 힙이 있음.
 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 사용된다.

 

 

우선순위 큐 구현 방식	삽입시간	삭제 시간
리스트	O(1)	O(N)
힙	O(log N)	O(log N)

 

 

 단계마다 '방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택'하기 위해 힙 자료구조 이용.
 다익스트라 알고리즘이 동작하는 '기본 원리는 동일'하다.
  -현재 가장 가까운 노드를 저장해 놓기 위해서 힙 자료구조를 추가적으로 이용한다는 점이 다름
  -현재의 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소 힙을 사용한다.

 

 

 힙 자료구조를 이요하는 다익스트라 알고리즘의 시간 복잡도는 O(E logV)입니다.

 노드를 하나씩 꺼내 검사하는 반복문은 노드의 개수 V이상의 횟수로는 처리되지 않는다.
  -결과적으로 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총횟수는 최대
 간선의 개수(E)만큼 연산이 수행될 수 있음.
 직관적으로 '전체 과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사'하다.
  -시간 복잡도를 O(E log E)로 판단할 수 있다.
  -중복 간선을 포함하지 않는 경우에 이를 O(E log V)로 정리할 수 있음.
  

 

---