목록heap (1)

늘 겸손하게

자료구조 - Heap

자료구조 heap 은 완전 이진트리를 기반으로 하는 자료 구조입니다. 많은 값들 중에서 최소 혹은 최대 값을 빠르게 찾는것이 가능한 자료 구조입니다. 일반적으로 힙은 두 가지 타입이 존재합니다. 1. Max-Heap Max-Heap의 루트 노드 값은 모든 자식 노드의 노드 값보다 커야 합니다. 이러한 속성은 모든 하위 트리도 만족해야 합니다. 2. Min-Heap Min-Heap의 루트 노드 값은 모든 자식 노드의 노드 값보다 작아야 합니다. 이러한 속성은 모든 하위 트리도 만족해야 합니다. 왜 힙을 쓰나요? 최대값 및 최솟값을 찾아내는 작업의 시간복잡도는 O(logN)으로 매우 빠릅니다. 새로운 원소를 저장하고 정렬하는데의 시간복잡도 또한 O(logN)으로 매우 빠릅니다. 그러므로 많은 데이터를 빠르게..
Algorithm 2022. 2. 9. 15:31
이전 Prev 1 Next 다음