자바에서의 힙 & 우선순위 큐

아래 글에서 자바에서의 힙 & 우선순위 큐에 대한 내용이 담겨 있습니다.
https://velog.io/@red-sprout/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Heap-Priority-Queue

구현

몇가지 성질을 활용하였습니다. 여기서 구현한 것은 최소힙입니다.

• Heap 배열은 인덱스가 1부터 시작하기에 크기가 n + 1이여야 합니다.
• 기본적으로 완전 이진트리기에 다음과 같습니다.
  • 왼쪽 자식 노드는 부모 * 2
  • 오른쪽 자식 노드는 부모 * 2 + 1

삽입(offer)

다음과 같은 힙 구조가 있습니다.

먼저 볼 수 있는 특징은 index 가 1부터 시작한다는 것입니다.
또한, 최소 힙이기에 기본적으로 모든 부모노드는 자식보다 작거나 같습니다.

여기에 3을 넣어봅시다.

우선 넣을 수 있는 공간(index = 5)에 3을 넣어줍니다.
그리고 부모노드와 자식노드를 비교하며 이를 서로 바꿔줍니다.
만약 자식노드가 부모노드보다 크다면 이 작업을 종료합니다.

여기서는 부모가 자식보다 작으므로 더이상의 교환 작업은 일어나지 않습니다.
그리고 부모의 인덱스는 무조건 자식 / 2 가 성립함을 확인할 수 있습니다.

삭제(poll)

여기서 값을 하나 빼서 반환해보겠습니다.

값을 빼는 것은 루트 노드(index = 1)의 값을 제거 후 반환해줍니다.
그리고 제거 후 정렬과정이 필요한데, 다음과 같습니다.

마지막 노드를 루트 노드 값이 없어지면 루트 노드 위치로 옮깁니다.

이 때 자식노드 중 우선순위가 앞서는 값(최소 힙의 경우 작은 값)을 기준으로, 부모와 자식간 비교를 하고 이 값을 서로 바꿔줍니다. 루트노드부터 이 과정을 거치는데, 만약 부모가 자식보다 작을 경우에는 이 과정을 중지합니다.

여기서는 3의 자식노드인 2와 4중 작은 2와 비교시 자식인 2가 작기 때문에 2와 교환을 합니다. 그리고나서는 최소힙의 모든 조건을 만족하기에 작업을 멈춰줍니다.

class MinHeap {
    private int[] arr;
    private int idx;
    
    public MinHeap(int n) {
        this.arr = new int[n + 1];
        this.idx = 1;
    }
    
    public int size() {
        return idx - 1;
    }
    
    public boolean isEmpty() {
        return this.size() == 0;
    }
    
    public void offer(int value) {
        arr[idx] = value;
        int current = idx;
        idx++;
        while(current > 1 && arr[current] < arr[current / 2]) {
            int tmp = arr[current / 2];
            arr[current / 2] = arr[current];
            arr[current] = tmp;
            current /= 2;
        }
    }
    
    public Integer poll() {
        if(isEmpty()) return null;
        int result = arr[1];
        int current = 1;
        idx--;
        arr[1] = arr[idx];
        while(current * 2 <= idx) {
            int children;
            if(current * 2 + 1 > idx) 
                children = current * 2;
            else 
                children = arr[current * 2] < arr[current * 2 + 1] ? current * 2 : current * 2 + 1;
            if(arr[current] < arr[children]) 
                break;
            int tmp = arr[children];
            arr[children] = arr[current];
            arr[current] = tmp;
            current = children;
        }
        return result;
    }
    
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for(int i = 1; i < idx; i++) {
            sb.append(arr[i]);
            if(i < idx - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}

Test

import java.io.*;

public class MyHeapTest {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        MinHeap pq = new MinHeap(n);
        
        System.out.println(pq.isEmpty()); // true
        
        pq.offer(5);
        System.out.println(pq); // [5]
        pq.offer(1);
        System.out.println(pq); // [1, 5]
        pq.offer(4);
        System.out.println(pq); // [1, 5, 4]
        pq.offer(2);
        System.out.println(pq); // [1, 2, 4, 5]
        pq.offer(3);
        System.out.println(pq); // [1, 2, 4, 5, 3]
        
        System.out.println(pq.isEmpty()); // false
        System.out.println(pq.size()); // 5
        
        while(!pq.isEmpty()) {
            pq.poll();
            System.out.println(pq);
        }
        
        br.close();
    }
}