힙(heap) 알고리즘

힙(heap)

• 완전 이진 트리
• 데이터 내에서 최솟값 및 최댓값을 찾아내는 연산을 빠르게 하기 위해 고안된 알고리즘
• 우선순위 큐를 위하여 만들어진 자료구조 (우선순위 큐?)
• 중복 허용
• 반정렬 상태 (느슨한 정렬 상태)를 유지함
  (부모노드의 값이 자식노드의 값보다 항상 크다/작다)
• 힙의 종류
• 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리(root)노드에 오게 된다.
  이를 응용하여 우선순위 큐와 같은 추상적 자료형을 구현

 

복잡도

• 시간복잡도 = O(log2 n)
• 삽입, 삭제의 시간복잡도는 O(1)이나, 
  heapify 하는 과정이 O(log2 n)
• heapify 과정에서 최대로 많은 연산 횟수를 한다면, 트리의 높이(레벨) 만큼 연산하기 때문에
  O(log2 n)

 

---

References

https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 

힙 (자료 구조) - 위키백과, 우리 모두의 백과사전