Heap

사전학습

---

PriorityQueue

• 큐를 활용한 자료구조.
• 데이터 들의 우선순위를 가지고 있다.
• 먼저 들어간 것이 먼저 나오는 것이 아니다.
• 우선순위를 지정할 수 있는 데이터의 기준을 정하여 우선순위가 높은 데이터가 먼저 나가는 자료구조.
• 힙을 사용하여 활용된 자료구조이다.

 

HEAP

---

• 완전 이진 트리이다.
  • ※마지막 레벨을 제외한 모든 서브트리의 레벨이 같고, 마지막 레벨은 무조건 왼쪽 부터 채워줘야 한다.
• 최대 힙과 최소 힙으로 이루어져 있다.
  • 최대 힙 : 루트노드로 올라 갈 수록 저장된 값이 커지는 구조.
  • 최소 힙 : 루트노드로 올라 갈 수록 저장된 값이 작은 구조.
• 최대 힙,최소 힙 둘다 노드에 우선순위가 가장 높은 것이 자리잡는다.
• 중복 된 값을 허용한다.(이진 탐색 트리에서는 중복이 허용되지 않는다.)

 

힙의 삽입/삭제 과정.O(log(n))

• 삽입 : 새 노드가 우선순위가 가장 낮다는 것을 가정을 하고 맨 왼쪽 끝에 위치 시킨다.
  • 부모노드와 비교를 하면서 위로 올라간다.

• 삭제 : 가장 우선순위가 높은 데이터를 먼저 제거한다.(최상단 루트 제거)
  • 최상단 루트가 지워지면서 나머지 트리의 원소들이 위치 이동이 필요하다.(힙 구조 유지)
  • 빈 공간에 가장 마지막 노드를 루트 노드로 지정한다.

 

 

 

 

chanhuiseok.github.io/posts/ds-4/