1. 특징 데이터에서 최댓값/최솟값을 빠르게 찾을 수 있는 완전 이진 트리 (complet binary tree) 완전 이진 트리란? 노드를 삽입할 때 최하단 왼쪽 노드부터 채워지는 트리 최댓값과 최솟값의 시간복잡도, 데이터 삭제 및 삽입의 시간복잡도는 $O(logn)$ (depth가 한 단계씩 내려가면서 체크횟수를 1/2로 줄여주기 때문) 값의 중복을 허용함 좌/우 노드 간 값의 크기는 상관 없음 2. 구조 최대 힙 Max heap / 최소 힙 Min heap 최대 힙 : 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다 (최소 힙은 반대 - 자식 노드보다 부모 노드의 값이 항상 같거나 더 작다) → 최댓값은 탐색할 필요도 없이 root node\ 3. 힙& 이진 탐색 트리의 비교 공통..
[자료구조] 힙 (Heap)
1. 특징 데이터에서 최댓값/최솟값을 빠르게 찾을 수 있는 완전 이진 트리 (complet binary tree) 완전 이진 트리란? 노드를 삽입할 때 최하단 왼쪽 노드부터 채워지는 트리 최댓값과 최솟값의 시간복잡도, 데이터 삭제 및 삽입의 시간복잡도는 $O(logn)$ (depth가 한 단계씩 내려가면서 체크횟수를 1/2로 줄여주기 때문) 값의 중복을 허용함 좌/우 노드 간 값의 크기는 상관 없음 2. 구조 최대 힙 Max heap / 최소 힙 Min heap 최대 힙 : 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다 (최소 힙은 반대 - 자식 노드보다 부모 노드의 값이 항상 같거나 더 작다) → 최댓값은 탐색할 필요도 없이 root node\ 3. 힙& 이진 탐색 트리의 비교 공통..
2022.07.27