[Tree] 이진 힙, Binary Heap

https://github.com/cuttingworms/Data-Structures-with-Python

GitHub - cuttingworms/Data-Structures-with-Python

- 이진 힙 (Binary Heap)

• 우선순위 큐(Priority Queue)를 구현하는 가장 기본적인 자료구조
  • 우선 순위우선순위 큐 (Priority Queue) : 가장 높은 우선순위를 가진 항목에 접근, 삭제와 임의의 우선순위를 가진 항목을 삽입할 수 있는 자료구조
    • 스택이나 큐도 일종의 우선 순위 큐
      • 스택 : 가장 마지막으로 삽입된 항목이 가장 높은 우선순위
      • 큐 : 가장 먼저 삽입된 항목이 가장 높은 우선순위
    • 왜 또 다른 우선순위 큐 자료구조가 필요한가?
      • 스택에 삽입되는 항목의 우선순위는 스택에 있는 모든 항목들의 우선순위보다 높음
      • 큐에 삽입되는 항목의 우선 순위는 큐에 있는 모든 항목들의 우선 순위보다 낮음
      • 삽입되는 항목이 임의의 우선순위를 가지면 스택이나 큐는 새 항목이 삽입될 때마다 저장되어 있는 항목들을 우선순위에 따라 정렬해야 하는 문제점이 있음
• 정의 : 완전 이진 트리로서 부모의 우선순위가 자식의 우선 순위보다 높은 자료구조

 

- 이진 힙의 종류

• 최소 힙 (Minimum Heap) : 키 값이 작을수록 높은 우선 순위
• 최대 힙 (Maximum Heap) : 키 값이 클수록 더 높은 우선 순위
  • 최소 힙의 루트 노드에는 항상 작은 Key가 저장됨

 

- 연산

• 최솟값 삭제
  1. 힙의 가장 마지막 노드, 즉 리스트의 가장 마지막 항목을 루트로 옮김
  2. 힙 크기 1 감소
  3. Downheap : 루트로부터 자식들 중 작은 값을 가진 자식과 키를 비교하여 힙 속성이 만족될 때까지 키를 교환하며 이파리 방향으로 진행
• 삽입
  1. 힙의 가장 마지막 노드, 즉 리스트의 가장 마지막 항목의 바로 다음 비어있는 원소에 새로운 항목을 저장
  2. Upheap : 루트 방향으로 올라가며 부모의 키와 비교하여 힙 속성이 만족될 때까지 노드를 교환 

 

- 상향식 힙 만들기 (Bottom-up Heap Construction)

• 핵심 아이디어
  • 상향식 방식으로 각 노드에 대해 힙 속성을 만족하도록 부모와 자식을 서로 교환
  • n개의 항목이 리스트에 임의의 순서로 저장되어 있을 때, 힙을 만들기 위해선 a[n//2]부터 a[1]까지 차례로 Downheap을 각각 수행하여 힙 속성을 충족시킴
    • a[n//2] ~ a[n]에 대하여 Downheap을 수행하지 않는 이유는, 이 노드들이 각각 이파리이므로 각 노드 스스로가 힙의 크기가 1인 최소 힙이기 때문

 

- 수행 시간

• 힙은 완전 이진 트리이므로 힙에 n개의 노드가 있으면 그 높이는 log(n+1)
• 각 힙 연산의 수행 시간은 O(log(n))