목록heap (1)

조금씩 꾸준히 완성을 향해

[자료 구조] 우선순위 큐(Priority Queue)와 힙(Heap)

우선선위 큐 (Priority Queue) 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용 예) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우 ▶ 우선순위 큐를 구현하는 방법은 다양하다. 1) 단순히 리스트를 이용하여 구현 가능 2) 힙(heap)을 이용하여 구현 가능 ▶ 데이터의 개수가 N개일 때, 구현 방식에 따라서 시간 복잡도 비교 힙(Heap)의 특징 완전 이진 이트 자료구조의 일종 힙에서는 항상 루트 노트(rooot node)를 제거 최소힙(min heap) : 루트 노트가 가장 작은 값을 가지는 힙 최대힙(max heap) : 루트 노트가 가장 큰 값을 가지는 힙 ▶ 완전 이진 트리 (Com..
DataStructure & Algorithm/이론 정리 2022. 10. 10. 19:13
이전 Prev 1 Next 다음