_05.힙(Heap) 구조

힙(heap)은 트리구조 중의 하나로,  '우선순위 큐(priority queue)를 구현할 때 사용됩니다. 우선 순위 큐는 데이터 구조의 하나로 데이터를 자유롭게 추가할 수 있습니다. 먼저, 우선순위에 대하여 살펴보겠습니다.

우선순위 큐(priority Queue)

• 우선 순위 큐는 우선 순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 입니다.
• 우선 순위 큐는 데이터를 우선 순위에 따라 처리하고 싶을 때 사용합니다.
  • 예) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우

자료구조	추출되는 데이터
스택(Stack)	가장 나중에 삽인된 데이터
큐(Queue)	가장 먼저 삽입된 데이터
우선순위 큐(Priority Queue)	가장 우선순위가 높은 데이터

• 우선 순위 큐를 구현하는 방법은 다양합니다.
  • 1) 단순히 리스트를 이용하여 구현할 수 있습니다.
  • 2)힙(heap)을 이용하여 구현할 수 있습니다. 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일합니다. (힙 정렬)
  • 이 경우 시간 복잡도는 O(NlogN) 입니다.

우선 순위 큐 구현방식	삽입방식	삭제시간
리스트	O(1)	O(N)
힙(Heap)	O(logn)	O(logN)

힙(Heap)의 특징

• 힙은  최댓값과 최솟값을 찾는 연산을 빠르게 하기위해 고안된 완전 이진 트리 자료구조의 일종입니다.
• 힙에서는 항상 루트 노드를 제거합니다.
• 최소 힙(min heap)
  • 루트 노드(부모 노드)가 가장 작은 걸 가집니다.
  • 따라서 값이 작은 데이터가 우선적으로  제거 됩니다.

• 최대 힙(max heap)
  • 루트 노드(부모 노드)가 가장 큰 값을 가집니다.
  • 따라서 값이 큰 데이터가 우선적으로 제거됩니다.

 

완전 이진 트리 (Complete Binary Tree)

• 완전 이진 트리란 루트(root)노드 부터 시작해서 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리를 의미합니다. 

최소 힙 구성 함수: Min - Heapify()

• (상향식) 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체합니다.

힙에 새로운 원소가 삽입될 때, 

• 새로운 원소가  삽입되었을 때, O(logN)의 시간 복잡도로 힙성질을 유지하도록 할 수 있습니다.

힙에서 원소가 제거될 때, 

• 원소가 제거되었을 때 O(logN)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있습니다.
  • 원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 합니다.
   

• 이후에 루트 노드에서 하향식으오 (더 작은 자식 노드로) Heapify ()를 진행합니다.

 

파이썬 힙 자료구조

힙 함수 활용하기 [python.flowdas.com/library/heapq.html]

• heapq.heappush(heap, item): item을 heap에 추가
• heapq.heappush(heap): heap에서 가장 작은 원소를 pop&리턴. 비어 있는 경우 iIndexError가 호출됨.
• heapq.heapify(x): 리스트 x를 즉각적으로 heap으로 변환함
• 코드 예제 보기 [github.com/AIFFEL-CodingMaster/sunny/blob/main/algorithms/5_Heap.ipynb]

 

마무리

• 힙(heap)구조 한 번에 인스톨하기 [유튜브 영상]
• 코드테스트 연습하기 [링크]