[파이썬 알고리즘 인터뷰] 15장 - 힙(heap)

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

• 힙의 특성을 만족하는 거의 완전한 트리(Almost Complete Tree)인 트리 기반 자료구조
  • 힙의 특성
    - 부모가 항상 자식보다 작거나 같다
  • 거의 완전한 트리
    - 완전 트리(Complete Tree)와 같은 의미
    - 포화 트리(Perfect Tree)에서 pefect와 complete의 단어적 의미 충돌로 인해 생겨난 말인듯 하다
    https://en.wikipedia.org/wiki/Binary_tree

Binary tree - Wikipedia

Some authors use the term complete to refer instead to a perfect binary tree as defined below, in which case they call this type of tree (with a possibly not filled last level) an almost complete binary tree or nearly complete binary tree.

 

• 파이썬에서 heap
  • 최소 힙만 구현되어 있음
    - 최소 힙 : 루트에 최소값이 오는 힙 구조
  • 우선순위 큐 ADT는 힙, 힙은 배열로 구현
    - 배열 -> 힙 -> 우선순위 큐
• 힙의 특징
  • 이진 힙(Binary heap)
    - 자식이 둘인 힙
    - 대부분 이진 힙이 사용
  • 힙이라는 자료구조는 힙 정렬의 부산물이라고 함
  • 완전 이진 트리
    - 레벨의 노드가 2배씩 증가
    - 배열로 구현시 이를 이용하여 인덱스를 구함
• 배열로 구현된 힙
  • 인덱스를 1부터 시작
    - 계산이 편함
    - 왼쪽 노드 : i * 2 / 오른쪽 노드 : i * 2 + 1
• 힙의 사용
  • 우선순위 큐
    - 다익스트라 알고리즘
  • 최소 신장 트리
    - 프림 알고리즘
  • 적절한 중간 레벨 노드 추출
    - 중앙값의 근사값
• 힙의 연산
  • 삽입
    - 가장 마지막 인덱스에 삽입 (완전 이진트리 특성 지키기)
    - 업힙(up-heap) : 부모 노드보다 작을 경우 인덱스를 바꾸는 과정을 반복 (힙의 특성 지키기)
    - log n
  • 추출
    - 루트 노드 pop
    - 가장 마지막 인덱스의 노드를 첫 인덱스(루트)에 위치시킴
    - 다운힙(down-heap) : 옮긴 루트노드가 자식노드보다 크면 인덱스를 바꾸는 과정을 반복 (힙 특성 지키기)
    - 다운힙은 왼쪽 자식부터 비교 (완전 이진트리 특성 지키기)
    - log n
• BST와 비교
  • BST는 좌/우 관계를 보장
  • 힙은 상/하 관계를 보장
  • BST는 삽입/탐색 모두 O(log n)
  • 힙은 최소값 탐색시 O(1)