우선순위큐 내부 구현

김형진·2023년 11월 26일
0

자바의 PriorityQueue는 내부적으로 힙(Heap)을 통해 구현된다.
힙은 최소 힙, 최대 힙으로 구분된다.

최소 힙 구현

아래는 Java로 구현된 최소 힙이다.

package baekjoon.class_.class3.최소힙;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        MinHeap heap = new MinHeap(100000);
        for(int i = 0; i<n; i++){
            int k = Integer.parseInt(br.readLine());
            if(k == 0) bw.write(heap.remove()+"\n");
            else heap.add(k);
        }
        bw.flush();
    }

    static class MinHeap{

        int[] arr;
        int size = 0;

        public MinHeap(int capacity){
            arr = new int[capacity];
        }

        public void add(int num){
            size++;
            arr[size-1] = num;
            compareWithParentAndSwap(size-1);
        }

        public int remove(){
            if(size == 0) return 0;

            int returnValue = arr[0];
            arr[0] = arr[size-1];
            arr[size-1] = 0;
            size--;
            compareWithChildAndSwap(0);
            return returnValue;
        }

        private void compareWithParentAndSwap(int childIndex){
            if(childIndex == 0) return;
            int child = arr[childIndex];
            int parentIndex = getParentIndex(childIndex);
            int parent = arr[parentIndex];

            if(child < parent){
                arr[childIndex] = parent;
                arr[parentIndex] = child;
                compareWithParentAndSwap(parentIndex);
            }
        }

        private void compareWithChildAndSwap(int parentIndex){
            int parent = arr[parentIndex];
            int leftChildIndex = getLeftChildIndex(parentIndex);
            int rightChildIndex = getRightChildIndex(parentIndex);

            if(rightChildIndex < size){ // 자식 노드가 모두 있는 경우
                int leftChild = arr[leftChildIndex];
                int rightChild = arr[rightChildIndex];
                if(leftChild < rightChild){
                    if(leftChild < parent){
                        arr[parentIndex] = leftChild;
                        arr[leftChildIndex] = parent;
                        compareWithChildAndSwap(leftChildIndex);
                    }
                }else{
                    if(rightChild < parent){
                        arr[parentIndex] = rightChild;
                        arr[rightChildIndex] = parent;
                        compareWithChildAndSwap(rightChildIndex);
                    }
                }
            }else if(leftChildIndex < size  && size <= rightChildIndex){ // 왼쪽 자식만 있는 경우
                int leftChild = arr[leftChildIndex];
                if(leftChild < parent){
                    arr[parentIndex] = leftChild;
                    arr[leftChildIndex] = parent;
                    compareWithChildAndSwap(leftChildIndex);
                }
            }
        }

        private int getParentIndex(int childIndex){
            return (childIndex-1) / 2;
        }

        private int getLeftChildIndex(int parentIndex){
            return (parentIndex * 2) + 1;
        }

        private int getRightChildIndex(int parentIndex){
            return (parentIndex * 2) + 2;
        }

    }

}

작동방식 설명

최소 힙은 자료구조 내 요소 중 가장 작은 값의 요소를 root에 위치시킨다.

조회
힙의 가장 첫 번째 요소(root) 리턴

insert
최소 힙에 요소를 삽입하여 정렬하는 과정은 다음과 같다.

  1. 맨 마지막 자리에 새로운 요소를 삽입한다.
  2. 해당 요소와 부모요소를 비교한다.
  3. 만약 새로 삽입된 요소가 부모요소보다 작은 수인 경우 서로의 위치를 바꿔준다.
  4. 해당 요소가 root에 위치하거나, 자신보다 작은 부모를 만날 때까지 2~3 과정을 반복한다.

delete
최소 힙의 첫 번째 요소를 삭제하는 과정은 다음과 같다.

  1. 첫 번째 요소를 제거한다.
  2. 마지막 요소(이하 A)를 root로 위치시키고, 원래 마지막 요소가 있던 자리는 0으로 초기화한다.
  3. A의 자식노드와 A 비교
    a. 자식노드가 모두 있는 경우(좌, 우) 자식노드 중 더 작은 노드와 비교
    b. 왼쪽 자식만 존재하는 경우, 왼쪽 자식과 A를 비교
  4. 만약 자식노드가 A보다 작은 경우 두 요소의 자리를 swap
  5. 자식노드와 비교하여 A가 더 작거나, 더 이상 비교할 자식노드가 없을 때까지 3~4과정 반복

시간 복잡도

조회
우선순위큐에서 가장 작거나 큰 요소를 조회하는 것은 root를 바로 가져오면 되므로, 시간복잡도가 1이다.

insert, delete
삽입 혹은 삭제는 이진트리로 구성된 자료구조의 각 계층을 순회하며 알맞은 자리를 찾아가기 때문에 logN의 시간복잡도를 가진다.

최대 힙 구현

최소 힙과 동일하게 구현하되, '최소'를 '최대'로, 혹은 '~보다 작다'를 '~보다 크다'로 바꿔주면 된다.

profile
히히

0개의 댓글