데이터 구조: 힙

힙은 가장 큰 요소를 항상 맨 앞에 두고 우선 순위에 따라 요소들을 구성하는 선형 데이터 구조입니다. 완전 이진 트리로 나타낸 힙은 각 부모 노드가 자식 노드보다 우선 순위가 더 높도록 보장합니다. 선택, 삽입, 삭제와 같은 연산은 트리를 오르내려 순서를 유지해야 하므로 복잡도가 O(log n)입니다. 우선 순위 변경도 복잡도가 O(log n)입니다. "올림" 알고리즘은 자신의 우선 순위가 부모보다 높을 경우 요소를 트리 위쪽으로 옮깁니다. "내림" 알고리즘은 자신의 우선 순위가 자식보다 낮을 경우 요소를 트리 아래쪽으로 옮깁니다. 삽입은 목록 끝에 새 요소를 추가하고 순서를 유지하기 위해 트리 위로 올리는 것을 포함합니다. 가장 우선 순위가 높은 요소를 삭제하는 것은 마지막 요소로 대체하고 순서를 유지하기 위해 그 요소를 내리는 것을 포함합니다. 힙은 목록을 정렬하여(O(n log n)) 또는 목록의 절반부터 트리의 내부 노드를 내려가(O(n)) 생성할 수 있습니다.