Heap과 Priority Queue

✏️ Heap 개요

• heap은 최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조이다.
  • 이진트리(binary tree)란 모든 노드의 최대 차수를 2로 제한한 것이다.
  • 완전이진트리(complete binary tree)란 마지막 레벨을 제외한 모든 노드가 채워져있으면서 모든 노드가 왼쪽부터 채워져있어야 한다.
    1. 마지막 레벨을 제외한 모든 노드가 채워져있어야 한다.
    2. 모든 노드들은 왼쪽부터 채워져있어야 한다.
  • 포화이진트리(perfect binary tree)란 마지막 레벨을 제외한 모든 노드는 두 개의 자식노드를 갖는다라는 조건을 가진다.

🔎 Heap 특징

• Heap의 핵심 특징은 부모 노드가 항상 자식 노드보다 우선순위가 높다는 것이다.
• 즉, 모든 요소들을 고려하여 우선순위를 정할 필요 없이 부모 노드는 자식 노드보다 항상 우선순위가 앞선다는 조건만 만족시키며 완전이진트리 형태로 채워나가는 것이다.
• 이는 곧 root node는 항상 우선순위가 높은 노드라는 것이다.
• heap의 종류로는 최소 힙과 최대 힙이 있다.

💻 Heap 구현

• 가장 표준적으로 구현되는 방식은 배열이다.
  • 왼쪽 자식 노드 index = 부모 노드 index * 2
  • 오른쪽 자식 노드 index = 부모 노드 index * 2 +1
  • 부모 노드 index = 자식 노드 index / 2
• add 메서드
  • heap의 삽입은 크게 두 가지로 나뉜다.
    • 사용자가 Comparator를 사용하여 정렬 방법을 힙 생성단계에서 넘겨받은 경우
    • 클래스 내에 정렬 방식을 Comparable로 구현했거나 기본 정렬 방식을 따르는 경우
  • sift-up (상향 선별)
    • 배열의 마지막 부분에 원소를 넣고 부모노드를 찾아가면서 부모 노드가 삽입 노드보다 작을때까지 교환해가면서 올라간다.
• remove 메서드
  • sift-down(하향 선별)
    • 아래로 내려가면서 재배치하는 과정
    • root에 있는 노드를 삭제하고, 마지막에 위치해있던 노드를 root Node로 가져와 add와는 반대로 자식노드가 재배치하려는 노드보다 크거나 자식노드가 없을때까지 자신의 위치를 찾아가면 된다.
    • 중요한 점은 왼쪽 자식 노드와 오른쪽 자식 노드 중 작은 값을 가진 노드랑 재배치할 노드와 비교해야 한다는 점이다. 그래야 최소 힙을 만족시킬 수 있다.

✏️ 우선순위 큐(PriorityQueue) 개요

• 우선순위 큐는 각 요소들이 각각의 우선 순위를 가지고 있고, 요소들의 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료구조이다.
• PriorityQueue를 사용하기 위해선 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface 를 구현해야 한다.
• Comparable Interface를 구현하면 compareTo method를 override하게되고, 해당 객체에서 처리할 우선순위 조건을 리턴해주면 PriorityQueue가 알아서 우선순위가 높은 객체를 추출해준다.
• PriorityQueue는 Heap을 이용하여 구현하는 것이 일반적이다.
  • 데이터 삽입시, 우선순위를 기준으로 기준으로 최대 힙 혹은 최소 힙을 구성하고, 데이터를 꺼낼때, 루트 노드를 얻어낸다.
  • 데이터 삭제시, 루트 노드를 삭제하고 빈 루트 노드 위치에 맨 마지막 노드를 삽입하고, 아래로 내려가면서 적절한 자리를 찾아 옮기는 방식으로 진행한다.
• 힙과 우선순위 큐의 차이점
  • 힙은 기본적으로 중점이 되는 것이 최솟값 또는 최댓값을 빠르게 찾기이다.
  • 우선순위 큐는 우선순위가 높은 순서대로 요소를 제공받는다는 점이다.
• 힙과 우선순위 큐
  • 우선순위 큐는 우선순위를 갖는 요소를 우선적으로 제공받을 수 있도록 하는 자료구조이다. 이는 리스트처럼 '추상적 모델' 개념에 좀 더 가깝고, 이를 구현하는 방식은 여러 방식이 있다.
  • 그 우선순위 큐를 구현하는데 있어서 가장 대표적인 구현 방식 힙 자료구조를 활용하는 방식이다.
  • 즉, 힙 자료구조를 이용한 우선순위 큐 구현이 맞는 말이다.
• 즉, 힙에서는 최대 혹은 최솟값을 빠르게 찾은 위한 것이 우선순위 큐에서는 우선순위가 높은 요소를 빠르게 찾기 위하다고 바꾸어 생각하면 된다.

🔎 PriorityQueue 특징

• 높은 우선순위 요소를 먼저 꺼내서 처리하는 구조이다.
  • 우선순위 큐에 들어가는 원소는 비교가 가능한 기준이 있어야한다. (comparator)
• 내부 요소는 힙으로 구성되어 이진트로 구조로 이루어져 있다.
• 내부구조가 힙으로 구성되어 있기때문에 시간 복잡도는 O(N*logN)이다.
• 우선순위를 중요하게 해야 하는 상황에서 주로 사용된다.

💻 PriorityQueue 동작

• add

• remove

인용

https://st-lab.tistory.com/205

자바 [JAVA] - 배열을 이용한 Heap (힙) 구현하기

https://st-lab.tistory.com/219

자바 [JAVA] - Priority Queue (우선순위 큐) 구현하기

https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90

[Java] Priority Queue(우선 순위 큐)

https://coding-factory.tistory.com/603

[Java] PriorityQueue(우선순위 큐) 클래스 사용법 & 예제 총정리