[자료구조] 힙(Heap)이란?

힙은 트리를 기반으로 하지만 변형된 형태의 정책을 채택한다. 힙(Heap) 정의 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리(Complete Binary Tree) 특징 > 힙을 이용해 최대값과 최솟값을 찾는 것은 O(logn)의 시간복잡도를 가짐 (cf. 배열 → O(n)) 활용 > 우선순위 큐와 같이, 최댓값이나 최솟값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현에 활용됨 힙의 구조 분류 최대 힙(Max Heap): 최댓값을 구하기 위한 구조 최소 힙(Min Heap): 최소값을 구하기 위한 구조 조건 각 노드의 값은 해당 노드가 가진 자식 노드의 값보다 크거나 같음(최대 힙의 경우) → 루트 노드가 최댓값을 가짐 완전 이진 트리의 형태(노드를 삽입할 때 왼쪽 노드부터 차례..

2021.05.30