Heap

Heap

개념

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
• 우선순위 큐를 구현하기 위하여 만들어진 자료구조
  • 우선순위 큐
    • 우선순위의 개념을 큐에 도입한 자료구조.
    • 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다.
    • 이용사례
      • 시뮬레이션 시스템
      • 네트워크 트래픽 제어
      • 운영 체제에서의 작업 스케쥴링
      • 수치 해석적인 계산
• 반정렬 상태(느슨한 정렬 상태) 를 유지한다.
  큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 - 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.
• 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)

시간 복잡도

• 삽입 : O(logN)
• 삭제 : O(logN)

힙의 종류

• 최대 힙
  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
  • key(부모 노드) >= key(자식 노드)
• 최소 힙
  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
  • key(부모 노드) <= key(자식 노드)