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

15 Dec 2023

java

이번에는 자바를 사용하여 최대 힙 알고리즘을 구현해보겠습니다.

최대 힙이란?

최대 힙(최댓값 힙)은 각 노드의 값이 해당 자식 노드들의 값보다 크거나 같은 완전 이진 트리를 의미합니다. 이를 통해 루트 노드는 항상 전체 트리에서 가장 큰 값을 갖습니다.

자바로 최대 힙 구현하기

import java.util.*;

public class MaxHeap {

    private List<Integer> heap;

    public MaxHeap() {
        heap = new ArrayList<>();
        heap.add(0); // 인덱스 0은 사용하지 않음
    }

    public void insert(int value) {
        heap.add(value);
        int idx = heap.size() - 1;
        while (idx > 1) {
            int parent = idx / 2;
            if (heap.get(parent) < heap.get(idx)) {
                swap(parent, idx);
                idx = parent;
            } else {
                break;
            }
        }
    }

    public int remove() {
        if (heap.size() <= 1) {
            return -1;
        }
        int removed = heap.get(1);
        heap.set(1, heap.get(heap.size() - 1));
        heap.remove(heap.size() - 1);

        int idx = 1;
        while (idx < heap.size()) {
            int left = idx * 2;
            int right = idx * 2 + 1;
            int maxIdx = idx;

            if (left < heap.size() && heap.get(left) > heap.get(maxIdx)) {
                maxIdx = left;
            }
            if (right < heap.size() && heap.get(right) > heap.get(maxIdx)) {
                maxIdx = right;
            }

            if (maxIdx == idx) {
                break;
            } else {
                swap(idx, maxIdx);
                idx = maxIdx;
            }
        }

        return removed;
    }

    private void swap(int i, int j) {
        int temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }
}

위의 코드는 ArrayList를 이용하여 최대 힙을 구현한 예시입니다.

참고 자료

자료구조와 함께 배우는 알고리즘 입문 자바 편 (저자: 문병로, 한빛미디어)

이제 위의 코드를 참고하여 자신만의 최대 힙 알고리즘을 만들어보세요!