[java] 자바 힙을 구현하기 위한 기본 자료구조

08 Dec 2023

java

자바 언어에서 힙(heap)을 구현하기 위해서는 기본적인 자료구조를 이해해야 합니다. 힙은 우선순위 큐, 힙 정렬 등의 다양한 알고리즘에 사용되는 중요한 자료구조입니다. 여기에서는 자바에서 힙을 구현하는 데 필요한 기본 자료구조와 구현 방법에 대해 알아보겠습니다.

배열을 이용한 힙 구현

가장 기본적인 힙 구현 방법 중 하나는 배열을 이용하는 방법입니다. 배열을 사용하여 이진 트리의 형태로 힙을 구현할 수 있습니다. 이진 트리는 각 노드가 최대 두 개의 자식을 가질 수 있는 트리 구조이므로 배열을 이용하여 힙을 구현할 수 있습니다.

public class MinHeap {
    private int[] heap;
    private int size;
    private int maxsize;

    public MinHeap(int maxsize) {
        this.maxsize = maxsize;
        this.size = 0;
        heap = new int[this.maxsize + 1];
        heap[0] = Integer.MIN_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 void print() {
        for (int i = 1; i <= size / 2; i++) {
            System.out.print(" PARENT : " + heap[i]
                    + " LEFT CHILD : " + heap[2 * i]
                    + " RIGHT CHILD :" + heap[2 * i + 1]);
            System.out.println();
        }
    }
}

위 코드는 최소 힙(MinHeap)을 배열을 이용하여 구현한 예시입니다.

링크드 리스트를 이용한 힙 구현

또 다른 방법으로는 링크드 리스트를 이용하여 힙을 구현하는 방법이 있습니다. 링크드 리스트를 사용하여 각 노드가 트리의 부모, 왼쪽 자식, 오른쪽 자식을 가리키도록 구현할 수 있습니다.

class HeapNode {
    int data;
    HeapNode left, right, parent;
 
    public HeapNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
        this.parent = null;
    }
}

public class MinHeapLinkedList {
    HeapNode root;
    HeapNode lastNode;

    public MinHeapLinkedList() {
        root = null;
        lastNode = null;
    }

    private void heapify(HeapNode node) {
        if (node.parent == null) {
            return;
        }

        if (node.data < node.parent.data) {
            int temp = node.data;
            node.data = node.parent.data;
            node.parent.data = temp;
            heapify(node.parent);
        }
    }

    public void Insert(int data) {
        HeapNode newNode = new HeapNode(data);
        if (root == null) {
            root = newNode;
            lastNode = newNode;
        } else {
            if (lastNode.left == null) {
                lastNode.left = newNode;
                newNode.parent = lastNode;
            } else {
                lastNode.right = newNode;
                newNode.parent = lastNode;
                lastNode = lastNode.parent;
                while (lastNode != null && lastNode.right != null) {
                    lastNode = lastNode.parent;
                }
            }
        }
        heapify(newNode);
    }
}

위 코드는 링크드 리스트를 이용하여 최소 힙(MinHeap)을 구현한 예시입니다.

결론

이와 같이 자바에서 힙을 구현하기 위한 기본적인 자료구조와 방법에 대해 알아보았습니다. 효율적인 알고리즘을 구현하기 위해서는 이러한 기본적인 자료구조를 이해하고 응용할 수 있는 능력이 필요합니다. 향후 더 많은 자료구조와 알고리즘을 공부하여 더 효율적인 프로그래밍을 할 수 있도록 노력해야 합니다.

더 많은 정보를 원하시면 다음 링크를 참고하세요.

배열을 이용한 힙 구현: GeeksforGeeks
링크드 리스트를 이용한 힙 구현: Tutorialspoint