[자료구조] 힙(Heap)이란

 

힙(Heap)을 배우기 전에 우선순위 큐를 알아둬야 한다. 

 

 

우선순위 큐(Priority Queue)

• 추상 데이터 타입 
• 우선순위가 부여되며, 우선순위가 높은 요소가 먼저 처리된다. 
• 예시 = 우선순위가 높은 작업부터 처리하기

 

 

우선순위 큐 구현 방식

• 배열이나 연결리스트로 구현
  
  • 삽입, 삭제 연산
    • 배열 = 삽입, 삭제하고 옆에 있는 데이터들을 옮겨주는 연산 -> O(N) 
    • 연결리스트 = 헤드 노드부터 삽입, 삭제할 위치까지 탐색하는 연산 -> O(N) 
• 힙으로 구현
  • 삽입, 삭제 연산 -> O(log N) 

배열과 연결리스트로 우선순위 큐를 구현하면 O(N)이 나올 수 있다. 

힙으로 우선순위 큐를 구현하면 O(log N)이 나온다. 

따라서 우선순위 큐는 힙으로 구현하는 것이 적합하다. 

 

 

힙(Heap)

• 이진 완전 트리(Complete Binary Tree)
• 각 노드의 값은 자식 노드의 값보다 크지 않거나, 작지 않다. 

 

 

힙 시간복잡도

• 삽입 = O(log N)
• 삭제 = O(log N)
• 최대/최소값 찾기 = O(1) 

 

 

힙 종류

• Max Heap
  • 각 노드의 값은 자식 노드의 값보다 작지 않다. (크다)
  • 루트 노드가 가장 큰 값을 가진다. 

Max Heap

 

 

• Min Heap 
  • 각 노드의 값은 자식 노드의 값보다 크지 않다. (작다)
  • 루트 노드가 가장 작은 값을 가진다. 

Min Heap