완전이진트리(링크)의 일종

이진탐색트리와 힙의 차이점

  • 이진탐색트리 : 탐색을 위한 자료구조
  • 힙 : 최대/최소값 검색을 위한 자료구조

최대값과 최소값을 빠르게 찾기 위한 자료구조

  1. 최대힙(max heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 (부모노드 : 최대값) 

  2. 최소힙(min heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 (부모노드 : 최소값) 

최대값 or 최소값 검색시 : O(1)
삽입, 삭제시 : O(logn)

우선순위 큐를 구현하는데 가장 효율적인 자료구조

  • 알고리즘
    1. 완전이진트리 구조에 맞추어 최하단부 왼쪽 노드부터 채워짐
    2. 채워진 노드 위치에서 부모 노드보다 값이 클 경우(최대힙일때)/ 작을 경우(최소힙일때), 부모 노드와 위치를 바꿈