Heap

---

• Heap은 최대값이나 최소값을 빠르게 찾아내기 위해 고안된 자료구조입니다. 힙은 완전 이진트리Complete Binary Tree의 일종으로, 부모 노드가 자식 노드보다 항상 큰 값최대 힙이나 작은 값최소 힙을 가지도록 구성됩니다.

특성

---

• 부모 노드의 값은 항상 자식 노드의 값보다 크거나 작다.

• 완전 이진트리이므로, 마지막 레벨을 제외한 모든 레벨이 꽉 차 있어야 한다.

• 최대 힙의 경우, 루트 노드의 값이 전체 트리에서 가장 큰 값이다.

• 최소 힙의 경우, 루트 노드의 값이 전체 트리에서 가장 작은 값이다.

종류

---

• 힙은 최대값이나 최소값을 찾는 방법에 따라 최대 힙과 최소 힙으로 나뉩니다.

• 최대 힙Max Heap

  • 부모 노드의 값이 자식 노드의 값보다 항상 큰 완전 이진트리를 말합니다.
  • 루트 노드는 전체 트리에서 가장 큰 값을 가집니다.

• 최소 힙Min Heap

  • 부모 노드의 값이 자식노드의 값보다 항상 작은 완전 이진트리를 말합니다.
  • 루트 노드는 전체 트리에서 가장 작은 값을 가집니다.

구현방법

---

• 힙은 배열이나 이진트리를 이용하여 구현할 수 있습니다.

• 배열을 이용한 구현

  • 부모 노드와 자식 노드 간의 관계를 인덱스로 표현하여 구현하는 방법입니다.
  • 완전 이진트리의 특성을 이용하여 각 노드를 배열의 인덱스로 매핑할 수 있습니다.

• 이진트리를 이용한 구현

  • 일반적인 이진트리 자료구조를 이용하여 구현하는 방법입니다.
  • 노드 클래스를 정의하고 각 노드의 부모 노드와 자식 노드를 참조하는 포인터를 이용하여 구현할 수 있습니다.

힙의 기본 연산

---

• 힙의 기본 연산에는 삽입, 삭제, 탐색이 있습니다.

• 삽입Insertion

  • 힙의 맨 끝에 새로운 값을 삽입한 후, 부모 노드와 비교하여 부모 노드의 값이 더 작은 경우, 부모 노드와 자리를 바꾸는 연산입니다.

• 삭제Deletion

  • 루트 노드를 삭제한 후, 힙의 마지막 노드를 루트 노드로 이동시키고 자식 노드와 비교하여 자식 노드의 값이 더 큰 경우, 자식 노드와 자리를 바꾸는 연산입니다.

• 탐색Search

  • 최대값 또는 최소값을 찾는 연산입니다. 최대 힙에서는 루트 노드의 값이 최대값이며, 최소 힙에서는 루트 노드의 값이 최소값입니다.

이진트리를 이용한 Min Heap 구현

---

public class MinHeap {

    private int[] heap; // 배열로 구현한 최소 힙
    private int size; // 힙의 크기

    public MinHeap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }

    public void insert(int value) {
        if (size == heap.length) {
            throw new IllegalStateException("Heap is full");
        }

        heap[size] = value;
        heapifyUp(size);
        size++;
    }

    public int deleteMin() {
        if (isEmpty()) {
            throw new IllegalStateException("Heap is empty");
        }

        int min = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown(0);
        return min;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    private void heapifyUp(int index) {
        int parentIndex = (index - 1) / 2;
        if (index > 0 && heap[index] < heap[parentIndex]) {
            swap(index, parentIndex);
            heapifyUp(parentIndex);
        }
    }

    private void heapifyDown(int index) {
        int leftChildIndex = 2 * index + 1;
        int rightChildIndex = 2 * index + 2;
        int smallestIndex = index;

        if (leftChildIndex < size && heap[leftChildIndex] < heap[smallestIndex]) {
            smallestIndex = leftChildIndex;
        }

        if (rightChildIndex < size && heap[rightChildIndex] < heap[smallestIndex]) {
            smallestIndex = rightChildIndex;
        }

        if (smallestIndex != index) {
            swap(index, smallestIndex);
            heapifyDown(smallestIndex);
        }
    }

    private void swap(int index1, int index2) {
        int temp = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = temp;
    }
}

• 위의 코드에서는 배열을 이용하여 최소 힙을 구현하였습니다.
• insert 메소드는 새로운 값을 배열의 끝에 삽입한 후, 부모 노드와 비교하여 부모 노드의 값이 더 큰 경우, 부모 노드와 자리를 바꾸는 연산을 수행합니다.
• deleteMin 메소드는 루트 노드를 삭제한 후, 힙의 마지막 노드를 루트 노드로 이동시키고 자식 노드와 비교하여 자식 노드의 값이 더 작은 경우, 자식 노드와 자리를 바꾸는 연산을 수행합니다.