힙(Heap)

• 완전 이진 트리의 일종
• 중복된 값을 허용
• Max Heap
  • 트리의 루트가 가장 큰값인 트리
• Min Heap
  • 트리의 루트가 가장 작은값인 트리
• 삽입
  • 가장 끝 칸에 새로운 데이터 삽입
  • 해당 위치부터 루트노드까지 올라가면서 종류에 맞게 값 변경
• 삭제
  • 루트 노드를 제거하는 것
  • 루트와 가장 끝칸의 노드의 값을 변경
  • 힙의 사이즈 1 감소
  • 루트 노드에서 다시 힙 구성
• 시간 복잡도
  • heapify
    • 힙 구성
    • 트리의 높이만큼 수행되므로 O(logn)
  • build heapify
    
    • O(nlogn)
      • 원소를 하나씩 넣고 힙 구성
    • O(n)
      • 모든 원소를 배열에 넣고 n/2번째 부터 힙 구성