5.5.1 힙 (Heap)

힙은 완전 이진 트리 기반의 자료구조 종류 : 최소힙, 최대힙 힙은 어떤 값이 들어와도 특정 힙의 규칙을 지키게 만들어져 있다.

• 최대힙 : 루트 노드에 있는 키는 모든 자식에 잇는 키 중 가장 커야함. 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야함.

  

  최대힙 예시 이미지

• 최소힙 : 루트 노드에 있는 키는 모든 자식에 잇는 키 중 최솟값이어야함. 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야함.

  

  최소힙 예시 이미지

최대힙의 삽입

힙에 새로운 요소가 들어오면 새로운 노드를 힙의 마지막 노드에 이어서 삽입. 이 새로운 노드를 부모 노드들과 크기를 비교, 교환하며 힙의 성질을 만족시킴.

최대힙 삽입 예시 이미지

• 삽입 과정
  1. 8이라는 값을 가진 노드 밑에 15 값을 가진 노드를 삽입
  2. 이 노드가 점점 올라가며 해당 노드 위에 있는 노드와 스왑, 최대힙 조건을 만족시킴

최대힙의 삭제

• 최대힙에서 최댓값 = 루트 노드.
• 루트 노드가 삭제, 그 이후 마지막 노드와 루트 노드를 스왑하는 과정을 거쳐 재구성.

5.5.2 우선순위 큐 (Priority Queue)

우선순위 큐 = 우선순위 대기열 이라고도 함. 대기열에서 우선순위가 높은 요소가 우선 순위가 낮은 요소보다 먼저 제공되는 자료 구조.

우선순위 큐 에시 이미지

• 우선순위 큐는 힙을 기반으로 구현됨

  • 우선순위에 따른 오름차순 정렬 = 최소힙(Min Heap) 으로 구현
  • 우선순위에 따른 내림차순 정렬 = 최대힙(Max Heap) 으로 구현

• 자료구조 비교

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

5.5.3 맵 (Map)

특정 순서에 따라 키(Key)와 매핑된 값(Value)의 조합으로 형성된 자료구조. Key : Value 형식으로 값 저장