one of the DataStructure
가장 큰값(혹은 작은값)의 노드를 빠르게 결정할 수 있도록 구조화된 Tree. 이런 성질을 유지하는데 드는 비용이 자료를 정렬된 상태로 유지하는 것보다 싸다.
힙(Heap)이란 수학적으로 표현하자면, 모든 k 에 대하여 heap[k] <= heap[2*k+1] 이고 heap[k] <= heap[2*k+2] 인 조건을 만족시키는 배열을 말한다. 결론적으로, 프로그래머에게 있어 중요한 사실은, heap[0]이 항상 최소값이 된다는 특성이다.
heap은 모든 자식노드들이 부모보다 작은 값을 갖는 Tree(일반적으로 BinaryTree)이다. 따라서 루트노드는 트리에서 가장 큰 노드이다. 각 분기내의 노드들은 정돈되어 있지만 어떤 단계의 노드들이 다른 단계의 노드들에 대해 정돈되어 있지 않으므로 이러한 트리를 부분정돈되었다고 한다.