[java] 자바로 힙 알고리즘 구현하기

15 Dec 2023

java

힙(Heap)은 트리 기반의 자료 구조로, 최솟값 또는 최댓값을 빠르게 찾기 위해 사용됩니다. 힙은 이진트리(binary tree)의 형태를 가지며, 부모 노드와 자식 노드 간의 관계에 특정한 규칙을 가지고 있습니다. 우선순위 큐(priority queue)와 같이 데이터를 우선순위에 따라 처리할 때 매우 유용하게 사용됩니다.

이제 자바로 간단한 힙 알고리즘을 구현해보겠습니다.

힙 알고리즘 구현

먼저, 힙 알고리즘을 구현하기 위해 Heap 클래스를 만들겠습니다.

class Heap {
    private int[] heap;
    private int size;
    private int maxsize;

    // 생성자
    public Heap(int maxsize) {
        this.maxsize = maxsize;
        this.size = 0;
        heap = new int[this.maxsize + 1];
        heap[0] = Integer.MAX_VALUE;
    }

    // 부모 노드 위치 계산
    private int parent(int pos) {
        return pos / 2;
    }

    // 왼쪽 자식 노드 위치 계산
    private int leftChild(int pos) {
        return (2 * pos);
    }

    // 오른쪽 자식 노드 위치 계산
    private int rightChild(int pos) {
        return (2 * pos) + 1;
    }

    // 리프 노드 여부 확인
    private boolean isLeaf(int pos) {
        return pos > (size / 2) && pos <= size;
    }

    // 노드 교체
    private void swap(int fpos, int spos) {
        int tmp;
        tmp = heap[fpos];
        heap[fpos] = heap[spos];
        heap[spos] = tmp;
    }

    // 최소 힙으로 재정렬
    private void minHeapify(int pos) {
        if (!isLeaf(pos)) {
            if (heap[pos] > heap[leftChild(pos)] || heap[pos] > heap[rightChild(pos)]) {
                if (heap[leftChild(pos)] < heap[rightChild(pos)]) {
                    swap(pos, leftChild(pos));
                    minHeapify(leftChild(pos));
                } else {
                    swap(pos, rightChild(pos));
                    minHeapify(rightChild(pos));
                }
            }
        }
    }

    // 삽입
    public void insert(int element) {
        heap[++size] = element;
        int current = size;
        while (heap[current] < heap[parent(current)]) {
            swap(current, parent(current));
            current = parent(current);
        }
    }

    // 최솟값 삭제
    public int remove() {
        int popped = heap[1];
        heap[1] = heap[size--];
        minHeapify(1);
        return popped;
    }
}

위의 코드는 인덱스 0은 사용하지 않고, 인덱스 1부터 사용하는 힙을 구현한 것입니다. insert 메서드를 통해 원소를 추가하고, remove 메서드를 통해 최솟값을 삭제할 수 있습니다.

힙 알고리즘 사용 예시

아래는 간단한 예시 코드입니다.

public class Main {
    public static void main(String[] arg) {
        Heap heap = new Heap(15);
        heap.insert(5);
        heap.insert(3);
        heap.insert(17);
        heap.insert(10);
        heap.insert(84);
        heap.insert(19);
        heap.insert(6);
        heap.insert(22);
        heap.insert(9);
        System.out.print("최소값 삭제: " + heap.remove());
    }
}

마무리

이상으로 자바를 이용하여 힙 알고리즘을 간단히 구현하는 방법에 대해 알아보았습니다. 힙 알고리즘은 데이터를 효율적으로 처리할 수 있는 강력한 도구이며, 자바를 사용하여 힙을 구현해보는 것은 프로그래밍 스킬 향상에 도움이 될 것입니다.

참고 자료: