힙 (자료구조)

부모 노드가 자식 노드보다 항상 크거나(최대 힙) 항상 작은(최소 힙) 완전 이진 트리다. 배열 하나에 그대로 담을 수 있어서 트리를 따로 만들지 않고도 맨 위 값(가장 크거나 가장 작은 값)을 바로 꺼낼 수 있고, 값을 넣거나 맨 위 값을 꺼낼 때마다 트리 높이만큼만 자리를 바꾸면 되므로 둘 다 O(log n)이 걸린다. 힙 정렬은 이 자료구조에서 맨 위 값을 하나씩 꺼내 정렬한다. JVM이 객체를 담는 메모리 영역인 [힙](/term/heap)과는 이름만 같고 다른 개념이다.