01. 우선순위 큐(Priority Queue)는 무엇?
일반적인 큐(Queue)의 "선입선출" 구조와 달리 우선순위 큐는 들어간 순서와 상관없이 어떤 기준으로 우선순위가 높은 데이터가 먼저 나오는 구조를 가지는 것을 말합니다!
우선순위 큐 구조는 힙!!(heap)이라는 자료구조를 가지고 구현이 가능합니다!
02. 힙(heap)은 무엇?
힙은 최솟값이나 최댓값을 빠르게 찾아내기 위해 고안된 완전 이진트리를 기본으로 한 자료구조입니다!!
-> 힙은 완전 이진트리이다??
-> 완전 이진트리는 간단하게 한 노드(점, 데이터 등등)에서 최대 두 개의 자식 노드(점, 데이터)를 연결하며 왼쪽에서 부터 채워나가는 형태의 알고리즘입니다!! (그림 참조)
아! 힙은 결국에 최소, 최댓값을 구하기 위한 것이고, 최소 값을 구하는 힙 구조를 "최소 힙", 최대 값을 구하는 힙 구조를 "최대 힙"이라고 부릅니다!
03. 최소 힙, 최대 힙
최소 힙이든, 최대 힙이든 원리는 동일합니다!!
최소 힙을 예를 들어서 최소 힙은 가장 작은!! 값을 우선순위로 구하는 것입니다. 그래서 추가된 노드는 부모 노드와 비교하면서 자기가 더 작다? 그러면 부모 노드와 자식 노드의 자리가 바뀝니다. 이렇게 자식 노드가 추가될 때마다 부모 노드랑 비교하여 완전 이진트리 (정삼각형 모양)의 최상단에 가장 작은 값이 구해지는 것이죠!!
최대 힙은?? 똑같습니다. 단 추가된 자식 노드가 부모 노드와 비교해서? 자식 노드가 크다면 부모 노드와 자리를 바꿔 나가겠죠, 최상단에는? 가장 큰 값이 구해지는 것이죠!!
백준 문제 풀어보시면서, 같이 공부해요!!
지적은 항상 배움의 시작입니다. 얼마든지 해주시면 감사합니다!!
