힙: 부모의 값이 자식의 값보다 항상 크다 혹은 항상 작다는 조건을 만족하는 완전이진트리.

당최 모르겠다. 트리도 모르는데 이진트리, 완전 이진트리라는 용어가 나온다.

개념정리

• 트리: 계층 구조(부모-자식)관계를 갖는 노드들의 집합.
• 노드: 노드는 데이터 구조에서 정보를 담고 있는 하나의 단위.
• 이진트리: 노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리
• 완전이진트리: 루트부터 노드가 채워져 있으면서 같은 레벨에는 왼쪽에서 오른쪽으로 노드가 채워져있는 이진트리

정리해본다면 힙이란 노드로 이루어진 집합체인데, 이 노드라는 녀석이 데이터와 다른 노드를 가르키는 포인터로 구성이 되있다고 한다. 그래서 여러 노드들이 모여서 트리라는 집합체를 만들게 된다. 그 때 부모 ~ 자식의 관계, 계층적인 구조를 가지게 된다. 그런데! 우리의 힙은 완전이진트리이기 때문에 마지막 레벨을 제외한 모든 레벨의 노드가 채워져있어야하고, 왼쪽 노드부터 채워진다고 합니다. 마지막으로! 부모 노드가 항상 자녀의 노드보다 크거나 항상 작기 때문에 원소를 삽입 시 해당 조건을 확인하여 노드간 데이터를 바꿔줍니다.

AI가 말아준 힙 구현 코드

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

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

    private int parent(int i) {
        return (i - 1) / 2;
    }

    private int leftChild(int i) {
        return 2 * i + 1;
    }

    private int rightChild(int i) {
        return 2 * i + 2;
    }

    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    public void insert(int value) {
        if (size == capacity) {
            System.out.println("Heap is full.");
            return;
        }
        heap[size] = value;
        size++;
        heapifyUp(size - 1);
    }

    private void heapifyUp(int index) {
        while (index > 0 && heap[parent(index)] > heap[index]) {
            swap(index, parent(index));
            index = parent(index);
        }
    }

    public void printHeap() {
        for (int i = 0; i < size; i++) {
            System.out.print(heap[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {1, 7, 2, 3, 4, 6, 5};
        MinHeap minHeap = new MinHeap(arr.length);

        System.out.println("Inserting elements into the heap:");
        for (int i = 0; i < arr.length; i++) {
            minHeap.insert(arr[i]);
            minHeap.printHeap();
        }
    }
}

insert 시 부모 노드를 찾아서 만약 부모 노드보다 값이 작을 경우 부모 노드와 자식 노드를 swap해주는 것을 확인할 수 있습니다.