[자료구조] 우선순위 큐와 최대힙, 최소힙(Max Heap, Min Heap)

Complete Binary Tree

완전 이진 트리란 각 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조로서 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 한다. 또한 최하단 레벨의 노드는 좌측만 노드가 채워져 있거나 좌측과 우측 모두 채워져 있어야 하며, 노드를 삽입할 때에는 최하단 좌측 노드부터 차례대로 삽입해야 한다.

 

Heap

힙이란 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리 자료구조를 갖으며 이러한 특성으로 여러개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾을 수 있다. 중복된 값을 허용하지 않는 이진 탐색 트리와는 달리 힙 트리에서는 중복 값을 허용한다는 특징이 있다. 

 

최대 힙(Max Heap)

부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 힙

 

최소 힙(Min Heap)

부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 힙

 

힙의 삽입 및 삭제

heap에 새로운 값이 추가되면 일단 마지막 노드에 이어서 삽입된다. 그 후 부모 노드와 크기 비교를 하여 교환 하는 과정을 반복하여 제 위치를 찾아간다. heap에서 삭제되는 값은 언제나 최대값 혹은 최소값이다. 삭제의 경우에는 마지막 노드에 위치한 값을 루트 노드 위치로 가져와서 자식노드와의 크기비교를 반복하여 힙을 재구성한다. 

 

 

우선순위큐

우선순위큐는 일반적인 큐의 경우 First-In-First-Out 인 것과 달리 들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 나가는 자료구조이다. 기본 세팅은 숫자든 문자열이든 오름차순 정렬이다. 최대힙 또는 최소힙을 사용하여 데이터를 내림차순 또는 오름차순으로 자동 정렬하여 데이터를 삽입 / 삭제한다.

 

우선순위에 배열을 저장하는 경우 Comparable을 implement하거나 람다표현식을 사용하여 특정 인덱스 기준으로 정렬하는 것이 가능하다. 

 

// 람다표현식을 사용하여 index = 1 을 기준으로 오름차순 정렬하는 경우

PriorityQueue<int[]> que = new PriorityQueue<>((a, b) -> {
	return a[1] - b[1];
    });
    
    
// 람다표현식을 사용하여 index = 2 을 기준으로 내림차순 정렬하는 경우

PriorityQueue<int[]> que = new PriorityQueue<>((a, b) -> {
	retusn b[2] - a[2];
    });