힙

메모리에서 데이터 스텍 힙 할때의 힙도 있지만.

트리 구조 가운데 힙이라는 것도 있다.

힙은 조금 특이한 형태의 트리(보통 이진 트리)이며,

노드의 각 자식의 값은 노드 자신의 값 이하여야 함( 루트는 그 트리에서 가장 큰 값)

때문에 최대값을 상수시간으로 구하는 것이 가능. (루트가 바로 그것)

검색은 O(n)이고, 이진탐색 트리처럼 주어진 노드 다음으로 큰 노드를 O(log(n))으로 찾는다던지, 

O(n)으로 모든 노드를 정렬된 순서로 출력은 불가능. 

(최대값을 계속 꺼내주면 정렬된 값을 얻을 수는 있겠지만, 최대값을 빼고 나서 다음 최대값을 찾아서 갱신해줘야 하기 때문에 불가능)

주어진 값들 중에서 빠르게 최대값을 추출해야 한다면 힙을 사용하면 좋다고 함.

책에서 예시를 봤는데 좋은 예시 같아서 기록

병원에서 대기중인 환자들이 있다. 

대기중인 환자들 중에는 간단한 상처때문에 온 환자도 있고, 심장마비 때문에 온 환자도 있다. 심장마비 환자에게 더 높은 우선순위를 부여하는 식으로 우선순위를 부여하여 힙에 넣는다. 의사가 다음 환자를 볼때 가장 우선순위가 높은 환자부터 치료를 시작한다. 힙에서 최대값을 꺼내기만 하면 우선순위가 가장 높은 환자를 찾을 수 있으며, 이 연산은 상수시간으로 처리된다.