힙

힙 (Heap)

• 힙은 완전 이진 트리로서 부모 노드 키값의 우선순위가 자식 노드 키 값의 우선순위보다 높은 자료 구조.
• 힙은 완전 이진 트리의 형태와 노드의 키 값에 대한 힙의 조건을 반드시 유지해야 한다.
•  완전 이진 트리 : 마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차있고, 마지막 레벨에는 노드들이 왼쪽부터 빠짐없이 채워진 트리.
• 힘의 종류
  • MAX 힙 : 키 값이 큰 항목이 우선순위가 높은 것으로 간주하므로 루트 노드의 키가 가장 큼
  • MIN 힙 : 키 값이 작은 항목이 우선순위가 높은 것으로 간주하므로 루트 노드의 키가 가장 작음

 

힙과 우선순위 큐

• 힙 자료구조는 파이썬에서 우선순위 큐를 구현하기 위해 사용된다.
• 우선순위 큐 : 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
• 활용 예시
  • 물건 정보가 있고, 물건 정보는물건의 가치와 무게로만 구성된다고 가정하자.
  • 모든 물건 데이터를 (가치, 물건)으로 묶어서 우선순위 큐 자료구조에 넣어 가장 가치가 높은 물건이 먼저 나오도록 할 수 있다. 
    
• MAX 힙 : 우선순위 값이 큰 데이터가 먼저 삭제됨
• MIN 힙 :  우선순위 값이 작은 데이터가 먼저 삭제됨 -> 파이썬 라이브러리의 기본 세팅!
  • 최소 힙을 최대 힙처럼 사용하기 위해 일부러 우선순위에 해당하는 값에 음수 부호를 붙이는 방법을 사용하기도 한다.