우선순위큐1 [알고리즘] 우선순위 큐, 힙 & 백준(최대 힙, 최소 힙, 가운데를 말해요, 카드 정렬하기) 우선순위 큐란, 데이터 삽입은 어떤 순서로 해도 상관없지만 데이터를 삭제할 때는 우선순위에 맞춰 더 높은 우선순위를 갖는 데이터를 먼저 삭제하는 큐를 말한다. 우선순위 큐는 힙을 통해 구현할 수 있다. 힙이란 완전 이진트리의 일종으로 대표적으로 최대 힙과 최소 힙이 있다. - 최대 힙: 루트 노드가 가장 큰 값을 가지며, 부모 노드는 항상 자식 노드보다 큰 값을 갖는다. - 최소 힙: 루트 노드가 가장 작은 값을 가지며, 부모 노드는 항상 자식 노드보다 작은 값을 갖는다. 힙에서의 삭제는 항상 루트 노드를 먼저 삭제하며 노드 변동 시 힙의 성질을 만족하도록 힙을 변동시킨다. 이러한 힙의 특징을 이용하여 우선순위 큐를 구현하는 것이다. 사실상 우선순위 큐를 구현하는 것은 힙을 구현하는 것이다. 최대 힙 구.. 2022. 10. 3. 이전 1 다음
