[자료구조] 우선순위 힙 -1

본문과 관련하여 실습한 전체코드는 리파지토리에 별도 작성하였습니다.

https://github.com/ejImDev/data_structure_study.git

우선순위 큐

가장 높은 우선순위를 가진 항목에 접근 및 삭제와, 임의의 우선순위를 가진 항목의 삽입을 지원하는 자료구조

• 스택이나 큐도 일종의 우선순위 큐
  
  • 스택 : 가장 마지막으로 삽입된 항목이 가장 높은 우선순위를 가지므로, 최근 시간일수록 높은 우선순위를 부여
    
  • 큐 : 먼저 삽입된 항목이 우선순위가 더 높음. 따라서 이른 시간일수록 더 높은 우선순위를 부여
    
    
• 스택과 큐가 있는데, 별도로 우선순위 큐가 필요한 이유
  
  • 스택에 삽입되는 항목의 우선순위에는 스택에 있는 모든 항목들의 우선순위보다 높음
    
  • 큐에 삽입되는 항목의 우선순위는 큐에 있는 모든 항목들의 우선순위보다 낮음
    
  • 삽입되는 항목이 임의의 우선순위를 가지면 스택이나 큐는 새 항목이 삽입될 때마다 저장되어 있는 항목들을 우선순위에 따라 정렬해야 하는 문제점이 있음 (ex. 힙 등…)
    
    

힙

대표적인 우선순위 큐

• 완전 이진트리
  
• 부모의 우선순위가 자식의 우선순위보다 높음
  
  

1. 최대힙 : 최소힙
   
   • 루트가 최대값:최소값을 가짐
     
   • 둘은 대칭적
     
   • 완전이진트리는 1차원 배열로 구현하며, 배열의 2번째 원소부터 사용
     
   • 완전이진트리의 노드들을 레벨순회 순서에 따라 a[1]부터 차례로 저장
   • 부모-자식 관계 계산법
     
     • a[i]의 자식은 a[2i]와 a[i+1]에 있음
       
     • a[j]의 부모는 a[j/2]에 있음. 단, j>1이고 j/2의 정수만을 취함
       
       

   1) 최소힙 : 키 값이 작을수록 높은 우선순위
   - 루트노드에는 항상 가장 작은 키가 저장됨
   - 부모 노드에 저장된 키가 자식 노드의 키보다 작다는 규칙 때문
   - 루트는 a[1]에 있으므로, O(1) 시간에 min 키를 가진 노드 접근
   
   

   2) 최대힙 : 키 값이 클수록 더 높은 우선순위
   
   

참고 자료 : ‘경기대학교 소프트웨어중심대학사업단 - JAVA 자료구조’ https://youtu.be/PAtgwNk9sY4