힙 Heap 자료구조

" 우선순위 Priority Queue를 구현하기 위하여 사용하는 자료구조 - Tree 자료구조 "

Tree 자료구조???
- 부모에서 자식으로 내려오는 계층적인 모델에 속한다.

 

- DFS/BFS 스택과 큐의 원리를 알아보았다.

https://cord-ai.tistory.com/158

DFS / BFS , Graph Structure

"스택"은 가장 나중에 삽입된 데이터가 가장 먼저 삭제(= FILO, LIFO)

"큐"는 가장 먼저 삽입된 데이터가 가장 먼저 삭제(= FIFO)

"우선순위 큐"는 우선순위가 가장 높은 데이터를 가장 먼저 삭제
So, 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다.

 

값이 큰 데이터가 먼저 추출됨

<예시>
여러 개의 물건 데이터를 자료구조에 넣었다가
가치가 높은 물건 데이터부터 꺼내서 확인해야 하는 경우를 가정해보자.
이런 경우에 우선순위 쿠 자료구조를 이용하면 효과적

- 이 물건 정보는 물건의 가치와 물건의 무게로만 구성된다고 가정
- 그러면 모든 물건 데이터를 (가치, 물건)으로 묶어서 우선수위 큐 자료구조에 넣을 수 있다.
- 이후 우선순위 큐에서 물건을 꺼내게 되면, 항상 가치가 높은 물건이 먼저 나오게 된다.

PriorityQueue 혹은 heapq를 사용할 수 있는데, 일반적으로 heapq를 사용 권장

(= 더 빠르게 동작하기 때문에)

- 우선순위 값을 표현할 때는 일반적으로 정수형 자료형의 변수가 사용된다.

대부분의 프로그래밍 언어에서는 우선순위 큐 라이브러리에 데이터의 묶음을 넣으면, 
첫 번째 원소를 기준으로 우선순위를 설정한다.
따라서, 데이터가 (가치, 물건)으로 구성된다면 "가치" 값이 우선순위 값이 되는 것이다.
또한 우선순위 큐를 구현할 때는 내부적으로  최소 힙 Min heap, 최대 힙 Max heap을 이용

최소 힙 = " 값이 낮은 데이터가 먼저 삭제 " = " 가장 값이 작은 원소를 추출 "

최대 힙 = " 값이 큰 데이터가 먼저 삭제 "

 

Python heap 라이브러리 = 최소 힙에 기반

- 다익스트라 최단 경로 알고리즘에서는 비용이 적은 노드를 우선하여 방문하므로

우선순위 큐 라이브러리를 그대로 사용하면 적합하다

https://cord-ai.tistory.com/165(= 다익스트라 방법 2)

https://cord-ai.tistory.com/142(= heapq)

Python 내장함수 및 라이브러리

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

데이터의 개수가 N개일 때, 힙 자료구조에 N개의 데이터를 모두 넣은 뒤에 다시 모든 데이터를 꺼낸다고 하자.
이때 시간 복잡도는 ???
삽입 O(logN), 삭제 O(logN)의 연산을 N번 반복하므로 O(NlogN)
따라서, 전체 연산 횟수는 대략 2NlogN으로 빅오 표기법에 따라 전체 시간 복잡도는 O(NlogN)