Heap

정의

트리 기반의 자료 구조

최소 힙 : 부모가 항상 자식보다 작거나 같음
최대 힙 : 부모가 항상 자식보다 크거나 같음

힙은 좌우 정렬되어 있는 것은 아님
단지 최대, 최소 힙에 따라 부모 - 자식간의 관계만 정의 되어 있음

이진 힙(Binary Heap) : 자식이 둘인 힙

힙 연산

최소 힙 기준

삽입

업힙(Up-Heap)
[1] 요소를 가장 하위 레벨의 최대한 왼쪽으로 삽입
[2] 부모 값과 비교해 값이 더 작은 경우 위치 변경
[3] 계속해서 부모 값과 비교해 위치 변경(가장 작은 값일 경우 루트까지 올라감)

추출

루트를 추출하면 됨
추출 후 힙의 특성을 유지하는 작업 때문에 시간 복잡도는 O(logn)
다운힙(Down-Heap) : 업힙의 반대 과정

이진 힙과 이진 탐색 트리의 차이점은?

• 이진 힙
  • 상/하 관계를 보장함
  • 최소 힙에서는 부모가 항상 자식보다 작음
  • 가장 큰 값 or 작은 값(최대, 최소 힙) 조회 시 사용 (O(1)에 가능)
• 이진 탐색 트리(BST, Binary Search Tree)
  • 좌/우 관계를 보장함
  • 부모는 왼쪽 자식보다는 크고 오른쪽 자식보다는 작거나 같음
  • 삽입, 탐색 모두 O(logN)에 가능
  • 모든 값이 정렬 되어야할 때 사용함

출처 : 파이썬 알고리즘 인터뷰