DataStructure - 힙(heap)

힙

• 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리를 말한다.

• 힙(heap)은 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다. 힙은 일종의 반 정렬 상태를 유지한다. 즉, 요소들이 완전히 정렬된 것은 아니지만 전혀 정렬되지 않은 것도 아닌 상태를 이용해 우선순위 큐를 구현한다. 힙의 시간 복잡도는 삽입과 삭제 모두  으로 다른 방법보다 상당히 유리하다. 여기서 다시 한 번 과 은 큰 차이가 있다는 것을 유념해야 한다. 만약 n 이 1024이고 알고리즘이 1024초가 걸린다면 알고리즘은 10초에 불과하다.

표현 방법	삽입	삭제
순서 없는 배열
순서 없는 연결 리스트
정렬된 배열
정렬된 열결 리스트
힙