힙 자료구조 구현 예시 코드 (최소힙 & 최대힙)

# 힙(heap)
- 완전이진트리 형태 -> 데이터의 연속성이 보장되서 배열(혹은 배열의 일종인 어레이 리스트)로 트리 작성하기 용이함
- 중복값 허용
- 반 정렬 상태 (형제 노드들 간의 정렬 X - 부모 노드와 자식 노드 같의 정렬만 O)
- 최소값 혹은 최대값을 빠르게 찾아내기 유용한 자료구조

// ArrayList 로 최소 힙 구현

import java.util.ArrayList;

class MinHeap {
    ArrayList<Integer> heap;

    public MinHeap() {
        this.heap = new ArrayList<>();
        this.heap.add(0); // 더미데이터삽입 -> 인덱스 기준으로 1번부터 사용하기 위함 !!
    }

    public void printTree() {
        for (int i = 1; i < this.heap.size(); i++) {
            System.out.print(this.heap.get(i) + " ");
        }
        System.out.println();
    }

    // 최소 힙 노드 삽입
    // 트리의 가장 끝(리프) 위치에 데이터 삽입 && 부모 노드와 키 비교한 후 작을 경우 부모 노드와 자리 교체 (반복)
    public void insert(int data) {
        heap.add(data);
        int curIdx = heap.size() - 1; //방금 insert한 대상의 인덱스 -> cur/2 == 부모인덱스
        // while조건 주의 -> //최상위 노드가 아니고, 부모보다 값이 작으면
        while (curIdx > 1 && heap.get(curIdx / 2) > heap.get(curIdx)) {
            int parentVal = heap.get(curIdx / 2);
            heap.set(curIdx / 2, heap.get(curIdx));
            heap.set(curIdx, parentVal);
            curIdx /= 2;
        }
    }

    public Integer delete() {
        if (heap.size() == 1) { // 더미 데이터만 있음
            System.out.println("Heap is empty");
            return null;
        }
        int target = heap.get(1); // 최소값
        // 마지막 데이터를 최상단으로 복사
        heap.set(1, heap.get(heap.size() - 1));
        // 마지막 데이터 삭제
        heap.remove(heap.size() - 1);

        int curIdx = 1;
        while (true) {
            int leftIdx = curIdx * 2;
            int rightIdx = curIdx * 2 + 1;
            int targetIdx = -1;

            if (rightIdx < heap.size()) {
                targetIdx = heap.get(leftIdx) < heap.get(rightIdx) ? leftIdx : rightIdx;
            } else if (leftIdx < heap.size()) {
                targetIdx = leftIdx;
            } else {
                break;
            }

            if (heap.get(curIdx) < heap.get(targetIdx)) {
                break;
            } else {
                int parentVal = heap.get(curIdx);
                heap.set(curIdx, heap.get(targetIdx));
                heap.set(targetIdx, parentVal);
                curIdx = targetIdx;
            }
        }
        return target;
    }
}

public class Main {
    public static void main(String[] args) {
        // Test code
        MinHeap minHeap = new MinHeap();
        System.out.println("== 데이터 삽입 ==");
        minHeap.insert(30);
        minHeap.insert(40);
        minHeap.insert(10);
        minHeap.printTree();
        minHeap.insert(50);
        minHeap.insert(60);
        minHeap.insert(70);
        minHeap.printTree();
        minHeap.insert(20);
        minHeap.printTree();
        minHeap.insert(30);
        minHeap.printTree();

        System.out.println();
        System.out.println("== 데이터 삭제 ==");
        System.out.println("삭제: " + minHeap.delete());
        minHeap.printTree();
        System.out.println("삭제: " + minHeap.delete());
        minHeap.printTree();
        System.out.println("삭제: " + minHeap.delete());
        minHeap.printTree();
    }
}