PriorityQueue 직접 구현해보기 (JAVA)

PriorityQueue는 각 요소가 우선순위를 가지는 큐로, 높은 우선순위를 가진 요소가 먼저 처리됩니다.
우선순위 큐는 위 그림과 같이 array, LinkedList, Heap으로 구현 할 수 있는데, Heap 방식 구현으로는 최악의 경우라도 O(logN)을 보장하기 때문에 일반적으로 힙(Heap) 자료구조를 사용합니다.

class Node {
    int data;
    int priority;

    public Node(int data, int priority) {
        this.data = data;
        this.priority = priority;
    }
}

public class MyPriorityQueue {
    private ArrayList<Node> heap;

    public MyPriorityQueue() {
        this.heap = new ArrayList<>();
    }

    // offer 메소드: 우선순위 큐에 요소를 추가합니다.
    public boolean offer(int data, int priority) {
        Node newNode = new Node(data, priority);
        heap.add(newNode);
        heapifyUp(heap.size() - 1);
        return true;
    }

    // poll 메소드: 우선순위가 가장 높은 요소를 제거하고 반환합니다.
    public Integer poll() {
        if (isEmpty()) {
            return null;
        }
        Node root = heap.get(0);
        Node lastNode = heap.remove(heap.size() - 1);
        if (!isEmpty()) {
            heap.set(0, lastNode);
            heapifyDown(0);
        }
        return root.data;
    }

    // peek 메소드: 우선순위가 가장 높은 요소를 반환하지만 제거하지는 않습니다.
    public Integer peek() {
        if (isEmpty()) {
            return null;
        }
        return heap.get(0).data;
    }

    // isEmpty 메소드: 큐가 비어있는지 확인합니다.
    public boolean isEmpty() {
        return heap.size() == 0;
    }

    // size 메소드: 큐의 크기를 반환합니다.
    public int size() {
        return heap.size();
    }

    // heapifyUp 메소드: 새로 추가된 요소를 힙의 올바른 위치로 이동시킵니다.
    private void heapifyUp(int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (heap.get(index).priority >= heap.get(parentIndex).priority) {
                break;
            }
            swap(index, parentIndex);
            index = parentIndex;
        }
    }

    // heapifyDown 메소드: 루트 요소를 힙의 올바른 위치로 이동시킵니다.
    private void heapifyDown(int index) {
        int lastIndex = heap.size() - 1;
        while (index <= lastIndex) {
            int leftChildIndex = 2 * index + 1;
            int rightChildIndex = 2 * index + 2;
            int smallestIndex = index;

            if (leftChildIndex <= lastIndex && heap.get(leftChildIndex).priority < heap.get(smallestIndex).priority) {
                smallestIndex = leftChildIndex;
            }

            if (rightChildIndex <= lastIndex && heap.get(rightChildIndex).priority < heap.get(smallestIndex).priority) {
                smallestIndex = rightChildIndex;
            }

            if (smallestIndex == index) {
                break;
            }

            swap(index, smallestIndex);
            index = smallestIndex;
        }
    }

    // swap 메소드: 두 노드의 위치를 바꿉니다.
    private void swap(int index1, int index2) {
        Node temp = heap.get(index1);
        heap.set(index1, heap.get(index2));
        heap.set(index2, temp);
    }
}

heapifyUp

heapifyUp 함수는 새로운 요소가 힙의 말단에 추가된 후, 해당 요소를 올바른 위치로 이동시켜 힙의 속성을 유지합니다. 힙의 속성은 부모 노드가 항상 자식 노드보다 작거나 같아야 한다는 것입니다.

동작 과정

• 삽입: 새로운 노드를 힙의 마지막 위치에 삽입합니다.
• 비교 및 스왑: 삽입된 노드를 부모 노드와 비교합니다. 만약 부모 노드보다 작다면 두 노드를 교환합니다.
• 반복: 이 과정을 루트 노드에 도달하거나 더 이상 부모 노드보다 작지 않을 때까지 반복합니다.

    private void heapifyUp(int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (heap.get(index).priority >= heap.get(parentIndex).priority) {
                break;
            }
            swap(index, parentIndex);
            index = parentIndex;
        }
    }

heapifyDown

heapifyDown 함수는 루트 노드가 제거된 후, 힙의 속성을 유지하기 위해 마지막 노드를 루트 노드로 이동시키고, 이 노드를 올바른 위치로 이동시킵니다.

동작 과정

• 루트 제거: 루트 노드를 제거하고, 힙의 마지막 노드를 루트 위치로 이동시킵니다.
• 비교 및 스왑: 새로운 루트 노드를 두 자식 노드와 비교합니다. 더 작은 자식 노드와 교환합니다.
• 반복: 이 과정을 리프 노드에 도달하거나 더 이상 자식 노드보다 작지 않을 때까지 반복합니다.

    // heapifyDown 메소드: 루트 요소를 힙의 올바른 위치로 이동시킵니다.
    private void heapifyDown(int index) {
        int lastIndex = heap.size() - 1;
        while (index <= lastIndex) {
            int leftChildIndex = 2 * index + 1;
            int rightChildIndex = 2 * index + 2;
            int smallestIndex = index;

            if (leftChildIndex <= lastIndex && heap.get(leftChildIndex).priority < heap.get(smallestIndex).priority) {
                smallestIndex = leftChildIndex;
            }

            if (rightChildIndex <= lastIndex && heap.get(rightChildIndex).priority < heap.get(smallestIndex).priority) {
                smallestIndex = rightChildIndex;
            }

            if (smallestIndex == index) {
                break;
            }

            swap(index, smallestIndex);
            index = smallestIndex;
        }
    }