DataStructure Heap / Programmers 코딩테스트 - 이중우선순위큐

자료구조 중 Heap을 공부하고 직접 구현한 코드와 Heap관련된 코딩테스트 문제를 후기로 남긴다.

---

Heap

우선, Heap은 완전 이중 트리 중 하나로 우선순위에 따라 정렬되는 자료구조이다. 깃허브 Heap 구현 코드를 작성해 두었다. 코드가 그다지 깔끔하다고는 할 수 없지만, 최소힙으로 필요한 부분은 대부분 구현해 두었다.

깃허브에 작성해 둔 것처럼 Heap과 우선순위 큐를 혼동할 수 있다. Heap은 구체적인 자료구조로 완전 이중 트리로 구현될 수 있다. 반면, 우선순위 큐는 추상적인 자료구조로 Heap, Array 등 다양한 방법으로 구현할 수 있다. Heap은 완전 이중 트리로 구현된 만큼 시간 복잡도가 O(log n)로 빠르다.

자바에서는 PriorityQueue 클래스가 Heap을 이용해 구현된 우선순위 큐이다. 우선순위에 따라서 큐가 정렬되며 기본적인 우선순위(최소값) 외에도 Comparator를 커스텀하여 PriorityQueue 클래스를 사용할 수 있다.

import java.util.*;

PriorityQueue<CustomObject> queue = new PriorityQueue<>(new Comparator<CustomObject>(){
	@Override
    public int compare(CustomObject o1, CustomObject o2){
    // 커스텀
    // o1가 앞에 온다면 양수, o2가 앞에 온다면 음수, 같으면 0 반환
    }
});

---

Programmers 코딩테스트 - 이중우선순위큐

- 문제 -
이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.
1. 명령어 : I 숫자, 실행 : 큐에 주어진 숫자를 삽입합니다.
2. 명령어 : D 1, 실행 : 큐에서 최댓값을 삭제합니다.
3. 명령어 : D -1, 실행 : 큐에서 최솟값을 삭제합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

제한사항
operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.operations의 원소는 큐가 수행할 연산을 나타냅니다.원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

Programmers에서 위와 같은 문제를 Heap을 이용해 해결하였다.
최소힙과 최대힙을 각각 구현하기 보다는 하나의 Array로 최소힙 정렬과 최대힙 정렬을 필요에 따라 적용하는 방법을 사용했다. 이렇게 구현하게 되면 최소 및 최대값을 번갈아가며 출력할 때, 시행횟수가 다소 많지만, 두 Arrays를 동시에 이용하는 것보다는 번거로움이 적고 힙의 시간복잡도가 빠른 것을 활용하여 구현하였다.

Dqueue라는 클래스를 직접 구현하였으며, 일반적인 Heap은 요소 추가시 항상 우선순위에 따른 정렬을 유지하지만 직접 구현한 클래스 에서는 시행횟수를 줄이기 위해 단순 추가만 하였다. 그리고 최소값과 최대값은 최소값 우선 정렬 및 최대값 우선 정렬을 이용해 구현해두었다.

문제풀이

import java.util.*;
class Dqueue{
    private int[] heap;
    private int size;
    private int capacity;
    
    public Dqueue(int initCapa){
        this.heap = new int[initCapa + 1];
        this.size = 0;
        this.capacity = initCapa;
    }
    
    private int parent(int idx){
        return idx / 2;
    }
    private int leftChild(int idx){
        return idx * 2;
    }
    private int rightChild(int idx){
        return idx * 2 + 1;
    }
    
    public void ensureCapa(){
        if(size >= capacity){
            capacity *= 2;
            heap = Arrays.copyOf(heap, capacity + 1);
            
        }
    }
    
    public void add(int element){
        ensureCapa();
        heap[++size] = element;
    }
    
    private void swap(int a, int b){
        int temp = heap[a];
        heap[a] = heap[b];
        heap[b] = temp;
    }
    
    private void maxSort(){
        int originSize = size;
        for(int i = size; i > 1; i--){
            maxUp(i);
        }
    }
    
    private void maxUp(int idx){
        int current = idx;
        while(current > 1){
            if(heap[current] > heap[parent(current)]){
                swap(current, parent(current));
                current = parent(current);
            } else{
                return;
            }
        }
    }
    
    private void minSort(){
        int originSize = size;
        for(int i = size; i > 1; i--){
            minUp(i);
        }
    }
    
    private void minUp(int idx){
        int current = idx;
        while(current > 1){
            if(heap[current] < heap[parent(current)]){
                swap(current, parent(current));
                current = parent(current);
            } else{
                return;
            }
        }
    }
    
    public int getMin(){
        if(size == 0){
            return 0;
        }
        minSort();
        int min = heap[1];
        heap[1] = heap[size--];
        return min;
    }
    
    public int getMax(){
        if(size == 0){
            return 0;
        }
        maxSort();
        int max = heap[1];
        heap[1] = heap[size--];
        return max;
    }
    
    public int[] getHeap(){
        if(size == 0){
            return new int[0];
        }
        return Arrays.copyOfRange(heap,1,size);
    }
}

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];
        Dqueue q = new Dqueue(1);
        for(String op : operations){
            switch (op.substring(0,1)){
                case "I" : q.add((int) Integer.valueOf(op.substring(2))); break;
                case "D" : if(op.substring(2).equals("1")){
                    int a = q.getMax();
                    // System.out.println(a);
                }else{
                    int b = q.getMin();
                    // System.out.println(b);
                }
            }
        }
        answer[0] = q.getMax();
        answer[1] = q.getMin();
        return answer;
    }
}

테스트 결과도 꽤 준수한 것을 볼 수 있다. 비록 구현해 두었으나 사용하지 않은 코드들도 있으니 그러한 부분은 참고하기를 바란다.

테스트 결과

---

공부 후기

자료구조를 공부하면서 공부한 자료구조를 직접 구현해보니 훨씬 더 이해가 잘된다. 그리고 막히는 부분은 이미 잘 구현된 코드를 보면서 부족한 부분을 공부하니 코드를 작성할 때, 발생하는 오류, 제한사항 등 아직은 신경쓰지 못하는 부분들도 세세하게 공부할 수 있어서 많은 도움이 되었다.