728x90
힙은 데이터의 최대값 혹은 최소값을 찾을때 사용한다. 그러므로 항상 최대값 혹은 최소값들이 필요한 문제에서는 힙을 사용한다.
max 힙 : 상위 부모 노드가 가장 큰것 그러므로 자식 노드가 부모보다 항상 작아야한다.
min 힙 : 상위 부모 노드가 가장 작은것 그러므로 자식 노드가 부모보다 항상 커야한다.
구조 : max 힙은 항상 큰값이 상위레벨 작은값이 하위레벨에 있다.
즉 max 힙을 구할때는 가장 큰값은 모든 자식보다 항상 커야한다.!! 그리고 모든 부모노드는 자식노드 보다 커야한다!!
완전이진트리라도 모든부모노드가 자식노드보다 크지않으면 max 힙이라고 말할수 없다.
추가 삭제가 o log(n)이므로
원소를 최대값에 빠르게 추가하거나 삭제할때 사용한다.
728x90