늘 겸손하게

우리가 흔히 아는 큐는 데이터가 rear에서 삽입되고 front에서 나가는(삭제) 선입선출(first-in first out) 구조의 자료구조입니다. 그렇다면 우선순위 큐(Priority Queue)는 무엇일까요? 우선순위 큐는 큐와 비슷하지만 다릅니다. 우선순위 큐의 모든 원소는 우선 순위가 있어 원소가 큐에서 제거되는 순서는 우선순위에 따라 결정됩니다. 보통 우선순위가 높은 원소가 가장 먼저 제거 대상이 됩니다. 그러므로 우선 순위 큐 내부의 모든 원소들은 오름차순, 혹은 내림차순으로 정렬된 채로 저장됩니다. 우선순위 큐를 구현하기 위해 다음과 같은 자료 구조를 이용할 수 있습니다. 배열 연결 리스트 (Linked List) 힙 ( Heap data structure ) 이진 탐색 트리 ( Binar..

자료구조 heap 은 완전 이진트리를 기반으로 하는 자료 구조입니다. 많은 값들 중에서 최소 혹은 최대 값을 빠르게 찾는것이 가능한 자료 구조입니다. 일반적으로 힙은 두 가지 타입이 존재합니다. 1. Max-Heap Max-Heap의 루트 노드 값은 모든 자식 노드의 노드 값보다 커야 합니다. 이러한 속성은 모든 하위 트리도 만족해야 합니다. 2. Min-Heap Min-Heap의 루트 노드 값은 모든 자식 노드의 노드 값보다 작아야 합니다. 이러한 속성은 모든 하위 트리도 만족해야 합니다. 왜 힙을 쓰나요? 최대값 및 최솟값을 찾아내는 작업의 시간복잡도는 O(logN)으로 매우 빠릅니다. 새로운 원소를 저장하고 정렬하는데의 시간복잡도 또한 O(logN)으로 매우 빠릅니다. 그러므로 많은 데이터를 빠르게..