개발노트

우선순위 큐란? 우선순위 큐는 먼저 들어온 데이터가 먼저 처리되는 일반적인 큐와 달리, 우선순위가 높은 데이터부터 처리되는 자료구조이다. 배열, 연결리스트, 힙(Heap)으로 모두 구현할 수 있지만 일반적으로는 시간복잡도가 적은 힙(Heap)을 사용한다. 힙(Heap) 힙(heap)은 힙의 특성(최소 힙에서는 부모가 항상 자식보다 작거나 같다)을 만족하는 거의 완전한 트리인 특수한 트리 기반의 자료구조이다. 최솟값, 최댓값을 찾아내는 연산을 빠르게 할 때 사용한다. 힙은 최소 힙(Min Heap)과 최대 힙(Max Heap)으로 구분할 수 있다. 힙은 정렬된 구조가 아니다. 부모-자식 간의 관계만 정의할 뿐, 좌우에 대한 관계는 정의하지 않는다. - 최소 힙: 루트노드가 가장 작은 값을 가지며, 항상 부..