1. Heaps?- 우선 힙을 저장하는 자료구조는 배열이다.- 일반적으로 이진 트리(Binary Tree)로 구현되는 완전 이진 트리의 형태다.- 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.- 구현을 쉽게 하기 위해 0인 인덱스는 사용하지 않고 1부터 사용된다.- 그림으로 나타내면 다음과 같다. (트리의 높이는 log(n)이 된다.) 2. 힙에서의 부모노드와 자식노드의 관계i번째 노드- 부모 노드 인덱스 : i//2- 왼쪽 자식 노드 인덱스 : 2*i- 오른쪽 자식 노드 인덱스 : 2*i + 13. Max Heap- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리 - 즉, 다음을 만족하는 Heap을 의미한다. A[parent(i)] >= A..
'완전 이진 트리' 태그의 글 목록