- 힙이란? //우선순위 큐라고도 한다.
완전 이진트리 구조로 루트노드부터 마지막 자식노드까지 오름차순 또는
내림 차순으로 이루어진 자료구조, 최대힙은 루트노드가 가장 큰값이고, 최소힙은 루트노드가 가장 작은 값이다.
운영체제의 작업스케줄링, 정렬, 에이스타에 사용된다.- 어떻게 구현할 것인가? 최대힙의 경우에 해당!
완전이진트리 구조로 이루어져 있어야 하므로 가장 낮은 위치에 속하는 노드에 데이터를 추가 후, 부모와의 대소관계를 비교 후 부모보다 데이터 가 트다면 swap하는 방식으로 루트노드까지 진행을 한다.
이런 구성이면 가장 높은 데이터가 루트노드에 위치하게 된다.
pop시에는 루트노드의 데이터를 차출하고, 루트 노드 하위 계층에 속한 left, right 간의 데이터를 비교해 높은 놈을 루트 노드에 위치한다.
- 어떻게 구현할 것인가? 최대힙의 경우에 해당!
- 우선순위큐 vs 큐
큐는 선형 구조로 되어 있지만, 우선순위 큐는 트리 구조로 되어 있다.
데이터 차출시에는 큐는 맨앞에 있는 데이터를 뽑아내고
우선순위큐의 경우는 root노드에 있는 데이터를 뽑아낸다.
🔥🔥🔥
0개의 댓글
관련 채용 정보
