SW 역량/자료구조 (1) 썸네일형 리스트형 힙(Heap)이란? 힙(Heap)이란? 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조 최댓값과 최솟값이 빠르게 알아내기 위한 목적으로 사용되는 자료구조! 어디에 사용하는데?? 일반적인 큐는 리스트 형태를 가지고 있기 때문에 원소의 최대/최소를 찾기 위해서는 O(N)이라는 시간복잡도가 발생한다. 하지만 힙을 사용하여 우선순위 큐를 나타내면 원소의 최대/최소를 찾기위해 O(logN)이라는 시간복잡도가 발생한다. 이는 힙의 최대/최소 탐색은 이진탐색트리를 통해 최대/최소의 원소를 찾는 작업과 같기 때문이다. (이진 탐색 트리는 왼쪽 자식은 더 작은 값, 오른쪽 자식은 더 큰 값으로 이루어져 있기에 힙과 배치 차이는 있음) 아무튼, 이러한 이유로 우선순위 큐는 대부분 힙으로 많이 .. 이전 1 다음
