[자료구조/JAVA] 우선순위 큐 : 힙(Heap)
우선순위 큐 (Priority Queue)
우선순위 큐는 일반적인 큐와 다르게, 우선순위 큐는 각 요소마다 우선순위가 지정되어 있어서, 우선순위가 높은 요소가 일반적으로 먼저 처리되는 형태의 자료구조이다.
요소들은 우선순위에 따라 정렬되어 있으며, 우선순위에 따라 삽입된 요소들이 정렬되어 있는 형태를 띈다.
스택과 큐 또한 일종의 삽입 순서에 따른 우선순위 큐의 종류라고 볼 수 있다.
힙(Heap)
힙은 대표적인 우선순위 큐의 종류이다. 주로 이진 힙으로 구현하며, 대표적인 종류로는 최소 힙과 최대 힙이 있다.
완전 이진 트리 : 힙은 완전 이진 트리의 구조를 가지고 노드가 왼쪽부터 차례로 채워진다.
최소 힙과 최대 힙: 최소 힙(Min Heap)의 경우 부모 노드의 값은 자식 노드의 값보다 항상 작거나 같아야 한다. 최대 힙(Max Heap)의 경우 그 반대이다.
삽입과 삭제: 새로운 요소를 삽입하거나 삭제할 때 힙의 속성을 유지하기 위해 부모 노드와 자식 노드의 우선순위를 비교하고 요소들을 재배치한다.
이진 힙은 완전 이진 트리이며, 이는 배열로 표현하기 좋은 구조이다.
1차원 배열로 표현하며, 배열의 2번째 원소(1번 인덱스)부터 사용하게 된다. 이는 인덱스 기반으로 트리의 부모-자식 관계를 정의하기 유용하다
- a[i]의 자식 노드 : a[2i], a[2i + 1]
- a[j]의 부모 노드 : a[j/2] (단 j>1, j/2의 정수만을 취함)
최소 힙 구현
최소 힙 구현 : 노드 표현
class Entry <Key extends Comparable<Key>, Value>{
private Key key;
private Value value;
public Entry(Key key, Value value){
this.key = key;
this.value = value;
}
public Key getKey() {
return key;
}
public void setKey(Key key) {
this.key = key;
}
public Value getValue() {
return value;
}
public void setValue(Value value) {
this.value = value;
}
}
완전 이진 트리를 구현해야 하므로, 노드 단위로 표현된다. 해당 코드는 노드를 표현했으며, Key와 Value를 가진다.
최소 힙 구현 : 이진 트리 구조 표현
class BinaryHeap<Key extends Comparable<Key>, Value>{
private Entry[] elements;
private int size;
public BinaryHeap(Entry[] ele, int size){
this.elements = ele;
this.size = size;
}
// 힙 사이즈
public int size(){
return size;
}
// 키 비교
private boolean greater(int i, int j){
return elements[i].getKey().compareTo(elements[j].getKey()) > 0;
}
//두 키의 위치 변경
private void swap(int i, int j){
Entry tmp = elements[i];
elements[i] = elements[j];
elements[j] = tmp;
}
// 힙 노드들 출력
public void print(){
for(Entry e : elements){
if(e == null){
continue;
}
System.out.print(e.getKey() + " ");
}
System.out.println();
}
}
힙 클래스를 만들어주고, 이진 트리 구조에 필요한 필드들와 메서드들을 만들어주었다.
필드 : Elements들을 담을 배열과 힙 크기를 필드로 가진다.
힙의 요소들을 모두 출력하는 함수와 사이즈를 반환하는 함수로 size()와 print()를 작성해주었다.
그리고 힙의 삽입 및 삭제 연산을 위해서 사용 될 Element들의 키값을 비교하는 메서드와, 키를 기반으로 두 개의 노드의 위치를 변경해주는 메서드인 greater()와 swap()을 작성해준다.
최소 힙 구현 : 삭제 연산(Dequeue)
최소 힙을 삭제하는 과정은 아래의 과정을 거친다.
- 루트의 키를 삭제
- 힙의 마지막 노드, 배열의 마지막 노드를 루트로 옮긴다. 그리고 힙 크기를 감소시킨다
- 루트로부터 자식들 중에서 작은 값을 가진 자식과 키를 비교하여 힙속성이 만족할 때 까지 키를 교환하며 Leaf 방향으로 진행한다.
해당 스왑 과정은 루트 노드부터 마지막 노드인 Leaf Node까지 이루어지며, 해당 과정을 다운힙(Downheap)이라고 부른다.
private void downheap(int i){
while(2 * i <= size){ // 자식 노드가 존재한다면
int k = 2 * i; // 자식 노드의 인덱스
//size보다 작으면 자식 노드가 존재하는 것. 두 개의 자식 노드를 비교하여 작은 자식 노드를 인덱스로 취함
if(k < size && greater(k, k+1)){
k++;
}
if(!greater(i, k)){ //최소힙을 유지하는 과정에서 자식 노드(k)가 부모 노드(i)보다 크다면 루프 중단
break;
}
swap(i, k); // 교환이 이루어짐
i = k; // 자식 노드를 부모 노드로 다시 설정하여 진행
}
}
public Entry dequeue(){
Entry min = elements[1];
swap(1, size); //가장 마지막 노드와 루트 노드 교환
elements[size] = null; //삭제하였으므로 루트와 교환한 인덱스를 null로 설정
size--; //사이즈도 줄임
downheap(1);
return min;
}
삭제(Dequeue) 연산은 아래의 과정을 거친다.
1. dequeue 연산 시, 정렬된 히프에서 루트 노드가 최소값이므로 이를 min으로 설정하고 이를 결과로 반환할 수 있도록 저장해둔다.
2. 가장 마지막 노드와 루트 노드를 교환한다.
3. 삭제 처리를 한다.
4. 루트 노드로부터 시작되는 Downheap을 진행한다.
5. 삭제한 최소값을 결과로 반환한다.
Downheap 과정
1. 현재 설정된 노드의 자식 노드가 존재한다면 루프를 돌린다.
2. 자식 노드 두 개를 비교하여 작은 자식 노드를 얻어낸다.
3. 현재 노드와, 2번에서 얻어낸 자식 노드를 비교
- 현재 노드가 자식 노드보다 우선순위가 높다면(값이 작다면 -> 최소 힙이므로) 루프를 중단한다.
- 현재 노드가 자식 노드보다 우선순위가 낮다면 둘을 교환한다. 그리고 자식 노드를 다시 현재 노드로 설정하고 루프를 진행한다.
최소 힙 구현 : 초기 힙 생성
// 힙 생성 (초기에 임의의 순서로 키가 저장되어 있는 배열의 항목을 최소힙으로 만듬)
public void createHeap(){
// Leaf 노드의 부모 노드부터 -> 부모 노드까지 downheap 진행
for(int i = size / 2; i > 0; i--){
downheap(i);
}
}
만약 초기에 생성자로 정렬되지 않은 형태의 Entry[] 배열이 들어와 힙의 형태가 아닌 경우, 이를 힙의 형태로 정렬하는 메서드이다.
이는 노드의 말단으로부터 위쪽으로 차례로 Downheap 연산을 수행하여 힙의 형태로 노드들을 정렬하게 된다.
[size / 2 ~ size]의 노드들은 Leaf Node이다. 따라서 정렬할 자식 노드가 없는 말단 노드이므로 정렬하지 않아도 된다.
따라서 [size/2 ~ 루트 노드]까지만 Downheap을 수행하면 된다.
최소 힙 구현 : 삽입 연산(Enqueue)
최소 힙에서 노드를 삽입하는 과정은 아래의 과정을 거친다.
- 힙의 마지막 노드 다음에 새로운 값 삽입
- 부모 노드와 비교하여 Root 방향으로 힙 속성을 만족할 때 까지 비교 및 Swap을 진행한다.
해당 스왑 과정은 마지막 노드인 Leaf Node로부터 루트 노드까지 차례로 이루어지며, 해당 과정을 업힙(Upheap)이라고 부른다.
public void enqueue(Key newKey, Value newValue){
Entry temp = new Entry(newKey, newValue);
elements[++size] = temp;
upheap(size); //삽입된 원소의 인덱스를 upheap으로 조정
}
private void upheap(int i){
while(i > 1 && greater(i/2, i)){
swap(i/2, i);
i = i/2;
}
}
삽입(Enqueue) 연산은 아래의 과정을 거친다.
1. 새로운 노드를 생성하고 이를 가장 마지막 인덱스에 삽입한다.
2. 삽입한 위치를 기점으로 Upheap을 수행하여 삽입된 노드의 위치를 조절한다.
Upheap 과정
루프는 현재 노드가 Root 노드가 아니고, 현재 노드가 부모 노드보다 크기가 클 때(-> 최소 힙이므로 정렬이 필요) 루프가 수행된다.
- 해당 루프가 수행되면 부모 노드가 자식 노드보다 크기가 작아야 하므로 교환이 수행된다.
- 그리고 현재 노드를 부모 노드의 인덱스로 설정하여 해당 과정을 반복한다.
- 만약 현재 노드가 부모 노드보다 크기가 작다면 루프가 중단되고 힙의 정렬이 완료될 것이다.
최소 힙 구현 : 전체 코드
class Entry <Key extends Comparable<Key>, Value>{
private Key key;
private Value value;
public Entry(Key key, Value value){
this.key = key;
this.value = value;
}
public Key getKey() {
return key;
}
public void setKey(Key key) {
this.key = key;
}
public Value getValue() {
return value;
}
public void setValue(Value value) {
this.value = value;
}
}
class BinaryHeap<Key extends Comparable<Key>, Value>{
private Entry[] elements;
private int size;
public BinaryHeap(Entry[] ele, int size){
this.elements = ele;
this.size = size;
}
public int size(){
return size;
}
// 키 비교
private boolean greater(int i, int j){
return elements[i].getKey().compareTo(elements[j].getKey()) > 0;
}
//두 키의 위치 변경
private void swap(int i, int j){
Entry tmp = elements[i];
elements[i] = elements[j];
elements[j] = tmp;
}
// 힙 생성 (초기에 임의의 순서로 키가 저장되어 있는 배열의 항목을 최소힙으로 만듬)
public void createHeap(){
// Leaf 노드의 부모 노드부터 -> 부모 노드까지 downheap 진행
// [size / 2 ~ size]의 노드들은 이파리노드이므로 비교할 노드가 없으므로 size/2부터 수행
for(int i = size / 2; i > 0; i--){
downheap(i);
}
}
private void downheap(int i){
while(2 * i <= size){ // 자식 노드가 존재한다면
int k = 2 * i; // 자식 노드의 인덱스
//size보다 작으면 자식 노드가 존재하는 것. 두 개의 자식 노드를 비교하여 작은 자식 노드를 인덱스로 취함
if(k < size && greater(k, k+1)){
k++;
}
if(!greater(i, k)){ //최소힙을 유지하는 과정에서 자식 노드(k)가 부모 노드(i)보다 크다면 루프 중단
break;
}
swap(i, k); // 교환이 이루어짐
i = k; // 자식 노드를 부모 노드로 다시 설정하여 진행
}
}
public void enqueue(Key newKey, Value newValue){
Entry temp = new Entry(newKey, newValue);
elements[++size] = temp;
upheap(size); //삽입된 원소의 인덱스를 upheap으로 조정
}
private void upheap(int i){
while(i > 1 && greater(i/2, i)){
swap(i/2, i);
i = i/2;
}
}
public Entry dequeue(){
Entry min = elements[1];
swap(1, size); //가장 마지막 노드와 루트 노드 교환
elements[size] = null; //삭제하였으므로 루트와 교환한 인덱스를 null로 설정
size--; //사이즈도 줄임
downheap(1);
return min;
}
public void print(){
for(Entry e : elements){
if(e == null){
continue;
}
System.out.print(e.getKey() + " ");
}
System.out.println();
}
}
public class C01_BinaryHeap {
public static void main(String[] args) {
Entry<Integer, String>[] elements = new Entry[16]; //0번째 인덱스는 사용안함
elements[1] = new Entry(60, "Grape");
elements[2] = new Entry(30, "Carrot");
elements[3] = new Entry(20, "Banana");
elements[4] = new Entry(70, "Lemon");
elements[5] = new Entry(80, "Monkey");
elements[6] = new Entry(10, "Apple");
elements[7] = new Entry(40, "Dog");
elements[8] = new Entry(50, "Frog");
BinaryHeap heap = new BinaryHeap(elements, 8);
System.out.println("Initialize");
heap.print();
heap.createHeap();
System.out.println("Create Heap");
heap.print();
System.out.println("Dequeue : " + heap.dequeue().getKey());
heap.print();
System.out.println("Dequeue : " + heap.dequeue().getKey());
heap.print();
System.out.println("Enqueue : 25");
heap.enqueue(25, "Bus");
heap.print();
System.out.println("Enqueue : 90");
heap.enqueue(90, "Nurse");
heap.print();
System.out.println("Dequeue : " + heap.dequeue().getKey());
heap.print();
}
}
Initialize
60 30 20 70 80 10 40 50
Create Heap
10 30 20 50 80 60 40 70
Dequeue : 10
20 30 40 50 80 60 70
Dequeue : 20
30 50 40 70 80 60
Enqueue : 25
25 50 30 70 80 60 40
Enqueue : 90
25 50 30 70 80 60 40 90
Dequeue : 25
30 50 40 70 80 60 90
'PS > 자료구조 & 알고리즘' 카테고리의 다른 글
| [자료구조/JAVA] 해시 테이블 (Hash Table) (0) | 2024.03.31 |
|---|---|
| [자료구조/JAVA] 허프만 코딩 (Huffman Coding) (0) | 2024.03.31 |
| [자료구조/JAVA] 트리 (3) : AVL 균형 트리 (AVL Tree) (0) | 2024.03.25 |
| [자료구조/JAVA] 트리 (2) : 이진 탐색 트리(Binary Search Tree, BST) (0) | 2024.03.21 |
| [자료구조/JAVA] 트리 (1) : 이진 트리(Binary Tree) : 순회 및 연산 (0) | 2024.03.19 |
