[Python 자료구조] 힙 (Heap)

⭐ 힙 (Heap)

1. 힙이란?

• 이진 트리의 한 종류 (이진 힙 - binary heap)
• 루트 노드가 언제나 최댓값 or 최솟값
• 완전 이진 트리여야 함

vs 이진 탐색 트리

• 원소들은 완전히 크기 순으로 정렬되어 있지 않고 느슨하게 정렬
• 특정 키 값을 가지는 원소를 빠르게 검색할 순 없다
• 완전 이진 트리여야 함
  
  

2. 추상적 자료구조 - 최대 힙 (Max Heap)

• __init__() : 빈 최대 힙을 생성
• insert(item) : 새로운 원소를 삽입
• remove() : 최대 원소 (root node)를 반환, 그리고 동시에 이 노드 삭제
  
  

3. 데이터 표현의 설계 - 배열 이용

• 노드 번호 m 을 기준으로,

  • 왼쪽 자식의 번호 : 2 * m
  • 오른쪽 자식의 번호 : 2 * m + 1
  • 부모 노드의 번호 : m // 2

• 완전 이진 트리 이므로, → 배열을 사용하는게 적당한 방법
  - 노드의 추가/삭제는 마지막 노드에서만
  
  

4. 원소의 삭제 - 최대 힙

• 루트 노드의 제거 → 이것이 원소들 중 최댓값
• 트리 마지막 자리 노드(오른쪽 제일 하단)를 임시로 루트노드 자리에 배치
• 복잡도
  - 원소의 개수가 n일때 → 자식 노드들과의 대소 비교 최대 회수 : 2 X log2n
  - 최악 복잡도 O(logn)
  
  

5. 최대/최소 힙의 응용

• 우선 순위 큐
  • Enqueue할 때 “느슨한 정렬”을 이루고 있도록 함 : O(logn)
  • Dequeue할 때 최댓값을 순서대로 추출 : O(logn)
• 힙 정렬
  • 정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입 : O(logn)
  • 삽입이 끝나면, 힙이 비게 될 때까지 하나씩 삭제 : O(logn)
  • 원소들이 삭제된 순서가 원소들의 정렬 순서
  • 정렬 알고리즘의 복잡도 : O(nlogn)