Heap / PriorityQueue

 

힙(Heap)은 특수한 이진 트리 기반의 데이터 구조입니다.

일반적으로 각 요소마다 우선순위가 할당되어 있는 배열로 구현됩니다. 힙의 구조는 최고

우선순위를 가진 요소가 항상 루트에 위치하도록 보장합니다(최대 힙 또는 최소 힙에 따라 가장 높은 우선순위 또는 가장 낮은 우선순위일 수 있음).

 

힙에서의 주요 작업은 요소를 삽입, 제거하고, 가장 높은 우선순위 요소를 확인하는 것입니다. 힙은 주로 우선순위 큐를 구현하는 데 사용됩니다. 왜냐하면 삽입 및 가장 높은(또는 낮은) 우선순위 요소의 검색과 같은 작업을 효율적으로 지원하기 때문입니다.

 

 

 

힙의 규칙:

• 힙은 비선형 컬렉션으로, 각 노드가 최대 k=2개의 자식을 가진 이진 트리입니다.

이진 탐색 트리는 다음 규칙을 따릅니다:  왼쪽 자식 < 부모 < 오른쪽 자식

 

힙 같은 경우 :

• 최소/오름차순 힙은 다음 규칙을 따릅니다:
  • 왼쪽 자식 > 부모 < 오른쪽 자식
  • 부모는 두 자식보다 작습니다.
  • 왼쪽 자식과 오른쪽 자식은 서로에 대해 정렬되지 않습니다 (순서가 중요하지 않으며, 부모보다 두 자식이 모두 크기만 하면 됩니다).
• 최대/내림차순 힙은 다음 규칙을 따릅니다:
  • 왼쪽 자식 < 부모 > 오른쪽 자식
  • 부모는 두 자식보다 큽니다.
  • 왼쪽 자식과 오른쪽 자식은 서로에 대해 정렬되지 않습니다 (순서가 중요하지 않으며, 부모보다 두 자식이 모두 작기만 하면 됩니다).

 

 

힙에서 요소 제거하기:

• 최소 힙에서는 최솟값(루트에 있는 값)만 제거할 수 있습니다.
• 제거된 후 대체할 노드를 찾아야 합니다. 어떤 노드를 선택해야 할까요?
• 복잡성: "힙 모양"을 유지해야 합니다. (밸런스 맞는 형태)
• 그래서 가장 오른쪽 리프 노드를 새로운 루트로 승격시켜 힙 모양을 유지합니다.
• 그런 다음 힙을 복원해야 합니다. 새롭게 승격된 노드를 양쪽 자식과 비교하고 가장 작은 값과 교환합니다.
• 노드가 양쪽 자식보다 작거나 리프 노드가 될 때까지 트리를 내려가는 과정을 계속합니다.

 

PriorityQueue

우선 순위가 있는 Queue 형 데이터 구조 즉 먼저 들어온 데이터가 먼저 나가는 구조를 가집니다.

PriorityQueue는 먼저 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조입니다. 

 

우선순위(Priority) 큐는 힙을 이용하여 구현하는 것이 일반적입니다. 데이터를 삽입할 때 우선순위를 기준으로 최대힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아서 옮기는 방식으로 진행됩니다.

 

• 가장 긴급한 우선순위를 가진 작업부터 항상 하나씩 얻습니다.

• 추가된 새 작업은 우선순위에 따라 트리 상단으로 밀려올립니다.

• 외부 관점에서 우선순위 큐는 전형적인 큐와 똑같이 느껴지고 보입니다.

 

그러나 enqueued된 요소/작업은 더 높은 우선순위를 가지면 큐에서 위로 밀려올라갑니다.

 

Priority Queue 값 추가

출처 : https://coding-factory.tistory.com/603#google_vignette

priorityQueue.add(1);     // priorityQueue 값 1 추가
priorityQueue.add(2);     // priorityQueue 값 2 추가
priorityQueue.offer(3);   // priorityQueue 값 3 추가
return answer;

 

 

 

Priority Queue 값 삭제

priorityQueue.poll();       // priorityQueue에 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueue.remove();     // priorityQueue에 첫번째 값 제거
priorityQueue.clear();      // priorityQueue에 초기화

poll()이나 remove()라는 메서드를 사용하면 됩니다. 값을 제거할 시 우선순위가 가장 높은 값이 제거됩니다. poll() 함수는 우선순위 큐가 비어있으면 null을 반환합니다. pop을 하면 가장 앞쪽에 있는 원소의 값이 아래 그림과 같이 제거됩니다. queue의 모든 요소를 제거하려면 clear() 메서드를 사용합니다.

 

 

 

Peek

priorityQueue.peek();       // priorityQueue에 첫번째 값 참조