목록heap (1)

개발자로 살아남기

우선순위 큐(Priority Queue)와 힙 (Heap)

우선순위 큐(Priority Queue)와 힙(Heap) 우선순위 큐 (Priority Queue) 기존의 큐와 다르게 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나옴 데이터간에 순서가 보장되지 않음 ex) 2, 3, 4, 1, 5 추가 후 iterator를 이용해 출력 시 1, 2, 4, 3, 5로 출력 구현방법 및 특징 - 배열 기반으로 구현 1) 인덱스로 데이터에 바로 접근할 수 있음 2) 데이터의 삽입/삭제에서 데이터들을 한칸씩 뒤로 밀거나 당기는 연산이 있어야 함 3) 삽입의 위치를 찾아내기 위해 최악의 경우 배열의 모든 데이터들과 우선순위를 비교해야 함 4) 저장 시 시간복잡도 O(n), 삭제 시 시간복잡도 O(1) - 연결리스트 기반으로 구현 1) 삽입의 위치를 찾기위해 최악의 경..
0x00. 자료구조 2021. 10. 27. 16:12
이전 Prev 1 Next 다음