bright jazz music

우선순위 큐(Priority Queue)우선순위 큐는 각 요소가 우선순위를 가지며, 우선순위가 높은 요소가 먼저 처리되는 자료구조다.다른 자료구조를 사용해도 되지만 이진 힙을 사용하는 것이 효율적이기 때문에 이진 힙으로 우선순위 큐를 구현하는 경우가 일반적이다. 아래 링크는 이진 힙 관련 포스팅:https://catnails.tistory.com/537  필수 구현 메서드:enqueue(value, priority) - 우선순위와 함께 새로운 요소 추가dequeue() - 가장 높은 우선순위의 요소를 제거하고 반환peek() - 가장 높은 우선순위의 요소를 반환isEmpty() - 큐가 비어있는지 확인 시간 복잡도:삽입(enqueue): O(log n)삭제(dequeue): O(log n)조회(peek)..

이진 힙은 트리의 일종이다.이진 힙은 이진 탐색 트리와 같이 두 개의 자식을 가진다.두 자식이 부모보다 작은 경우, 즉 루트가 최대 크기가 되는 힙이 최대 힙이다.자식들이 부모보다 큰 경우 최소 힙이며 이 경우, 루트가 최소값이 되는 최소힙이다.이진 힙은 이진 탐색트리와는 다르게 두 자식을 나누는 기준이 없다. 좌우로 나누는 기준은 없다는 것이다. 그저 부모보다 크거나 작기만 하면 된다. 특정 인덱스를 가진 노드의 자식 노드의 인덱스를 확인하려면 아래와 같은 식을 따르면 된다.왼쪽 자식: 2n + 1오른쪽 자식: 2n + 2 역으로 자식 노드에서 부모 노드를 찾으려면부모 노드의 인덱스를 사용해 자식 노드의 인덱스를 구하는 방식을 역으로 하면 된다. 즉 2n+1을 역으로 하면 된다.(n-1)/2 을 하고..