목록힙 (1)

개발기록장

[자료구조] 우선순위 큐와 힙

우선순위 큐 우선순위 큐는 일반적인 큐와 다르게 우선 순위가 높은 요소가 먼저 나가는 개념이다. 여기서 주의할 점은 우선순위 큐는 자료구조가 아닌 개념이다. 따라서 우선순위 큐를 구현하는 방법은 다양하게 존재할 수 있다. 그중 힙은 우선순위 큐를 구현하기 위한 가장 적합한 방법이다. 힙 (Heap) 힙은 자료구조이며, 이진 트리 형태이다. 우선순위가 높은 요소를 루트에 두기위해 요소가 삽입, 삭제될 때 바로 정렬되는 특징이 있다. 힙의 특징 우선순위가 가장 높은 것을 루투에 두고, 항상 루트가 먼저 나간다. 루트가 가장 큰 값이 되는 최대 힙과 루트가 가장 작은 값이 되는 최소 힙 두가지로 나뉜다. (오름차순이냐 내림차순이냐 정도의 차이) 파이썬에서는 heapq 혹은 PriorityQueue 모듈을 통해..
TIL/알고리즘 with 파이썬 2023. 1. 15. 22:41
이전 Prev 1 Next 다음