자료구조1 [자료구조] 우선순위 큐 - 작성 중 큐는 FIFO, 우선순위 큐는 우선순위가 높은거 먼저 나옴 구현 1. 리스트를 이용한 구현 (큐로도 가능?) 2. 힙을 이용한 구현 시간 복잡도 1 -> 0(1), 삭제 시는 O(N) // 찾아서 삭제해야됨 2. -> O(log N) / O(log N) -> 삽입 삭제가 시간복잡도 동일하고 데이터의 입출력 과정이 힙정렬과 동일, 이때는 O(N log N) 힙은 완전 이진트리의 일종, 항상 루트 노드 제거 최소 힙은 루트 노드가 가장 작은 값을 가짐, 값이 작은 데이터가 우선 제거됨 ㄴ 넣었다 빼면 걍 오름차순 최대 힙은 루트 노드가 가장 큰 값이고 값이 가장 큰 데이터가 우선 제거됨, 내림차순 완전이진트리 : 루트부터 왼쪽, 오른쪽으로 순서대로 데이터가 삽입되는 트리 최소힙 구성함수 (min-heapif.. 2022. 4. 11. 이전 1 다음