최대힙

[자료구조] 우선순위 큐(Priority Queue), 그리고 힙(Heap)

우선순위 큐(Priority Queue) : 가장 높은 우선순위를 가진 항목에 접근과 삭제, 임의의 우선순위를 가진 항목 삽입을 지원하는 자료구조이다. 큐(Queue)라고 함은 먼저 들어오는 데이터가 먼저 나가는 자료구조인데, 앞에 우선순위가 붙어서 먼저 들어오는 데이터가 아닌 우선순위가 높은 데이터가 먼저나가는 구조인것이다. 힙(Heap)이란 우선순위 큐를 위해서 고안된 완전이진트리 형태의 자료구조이다. 또한 부모의 우선순위가 자식의 우선순위 보다 크다는 특징을 가지고 있어 우선 순위 큐를 구현하는데 힙을 주로 사용한다. 힙의 종류는 두가지가 있다. 최소 힙(Minimum Heap) : 키가 작을수록 높은 우선순위 Key(부모노드) < Key(자식 노드) 최대 힙(Maximum Heap) : 키가 클 ..