[자료구조] 힙(Heap)

힙(Heap)

• 완전 이진 트리 형태
  • 중복 값 허용
  • 반 정렬 상태
• 최솟값 또는 최댓값을 빠르게 찾아내는데 유용한 자료구조
  • 최소 힙, 최대 힙
• 우선순위 큐(Priority Queue)를 구현하는데 사용

최소 힙(Min Heap)

부모 노드의 키가 자식 노드의 키보다 작거나 같은 형태 (루트 노드가 최소값을 가지는 힙)

최대 힙(Max Heap)

부모 노드의 키가 자식 노드의 키보다 크거나 같은 형태 (루트 코드가 최대값을 가지는 힙)

힙 구현

• 배열을 사용하여 구현
• 완전 이진트리의 특성에 따라 배열에서 각 노드는 인덱스로 표현
• 루트 노드는 인덱스 0에 위치하며, 자식 노드들은 특정한 방식으로 인덱스를 계산하여 배열에 저장

# 부모 노드와 자식 노드의 관계

왼쪽 자식 index = 부모 index * 2
오른쪽 자식 index = (부모 index * 2) + 1
부모 index = 자식 index / 2

힙의 삽입

• 힙의 맨 끝에 요소를 추가
• 부모 노드와 비교하여 힙 속성을 유지

힙의 삭제

• 힙에서 최대값 또는 최소값을 제거
• 루트 노드를 제거한 후, 마지막 노드를 루트로 이동시킨 후 자식 노드들과 비교하여 힙 속성을 유지

최소 힙 삽입 & 삭제 코드

class MinHeap {
    private int[] heap;
    private int maxSize;
    private int size;

    public MinHeap(int maxSize) {
        this.maxSize = maxSize;
        this.size = 0;
        this.heap = new int[maxSize + 1];
    }

    public void insert(int value) {
        if (size >= maxSize) {
            System.out.println("Heap is full, cannot insert more elements.");
            return;
        }

        size++;
        int currentIndex = size;
        heap[currentIndex] = value;

        while (currentIndex > 1 && heap[currentIndex] < heap[currentIndex / 2]) {
            swap(currentIndex, currentIndex / 2);
            currentIndex = currentIndex / 2;
        }
    }
    
    public int deleteMin() {
        if (size == 0) {
            System.out.println("Heap is empty, cannot delete any element.");
            return -1;
        }

        int deletedValue = heap[1];
        heap[1] = heap[size];
        size--;

        int currentIndex = 1;
        while (true) {
            int leftChild = 2 * currentIndex;
            int rightChild = 2 * currentIndex + 1;
            int smallest = currentIndex;

            if (leftChild <= size && heap[leftChild] < heap[smallest]) {
                smallest = leftChild;
            }

            if (rightChild <= size && heap[rightChild] < heap[smallest]) {
                smallest = rightChild;
            }

            if (smallest != currentIndex) {
                swap(currentIndex, smallest);
                currentIndex = smallest;
            } else {
                break;
            }
        }

        return deletedValue;
    }

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

최대 힙 삽입 & 삭제 코드

class MaxHeap {
    private int[] heap;
    private int maxSize;
    private int size;

    public MaxHeap(int maxSize) {
        this.maxSize = maxSize;
        this.size = 0;
        this.heap = new int[maxSize + 1];
    }

    public void insert(int value) {
        if (size >= maxSize) {
            System.out.println("Heap is full, cannot insert more elements.");
            return;
        }

        size++;
        int currentIndex = size;
        heap[currentIndex] = value;

        while (currentIndex > 1 && heap[currentIndex] > heap[currentIndex / 2]) {
            swap(currentIndex, currentIndex / 2);
            currentIndex = currentIndex / 2;
        }
    }

    public int deleteMax() {
        if (size == 0) {
            System.out.println("Heap is empty, cannot delete any element.");
            return -1;
        }

        int deletedValue = heap[1];
        heap[1] = heap[size];
        size--;

        int currentIndex = 1;
        while (true) {
            int leftChild = 2 * currentIndex;
            int rightChild = 2 * currentIndex + 1;
            int largest = currentIndex;

            if (leftChild <= size && heap[leftChild] > heap[largest]) {
                largest = leftChild;
            }

            if (rightChild <= size && heap[rightChild] > heap[largest]) {
                largest = rightChild;
            }

            if (largest != currentIndex) {
                swap(currentIndex, largest);
                currentIndex = largest;
            } else {
                break;
            }
        }

        return deletedValue;
    }

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