힙(Heap)

힙(Heap)

• 완전 이진 트리 형태
• 중복 값 허용
• 반 정렬 상태
• 최소/최대 힙에 따라 레벨간 정렬을 되지만
• 레벨 내 정렬은 되지 않는다.
 

• 최소값 또는 최대값을 빠르게 찾아내는데 유용한 자료구조
• 최소 힙, 최대 힙
 

최소 힙(Min Heap)

• 부모 노드의 키가 자식 노드의 키보다 작거나 같은 형태

최대 힙(Max Heap)

• 부모 노드의 키가 자식 노드의 키보다 크거나 같은 형태

힙 기본 연산

최소 힙 - 삽입

• 트리의 가장 끝 위치에 데이터 삽입

• 부모 노드와 키 비교한 후 작을 경우 부모 자리와 교체(반복)

최소 힙 - 삭제

• 최상위 노드 반환 및 삭제

• 가장 마지막 위치의 노드를 최상위 노드로 위치 시킴

• 자식 노드 중 작은 값과 비교 후 부모 노드가 더 크면 자리 교체(반복)

ArrayList를 통한 Heap 코드 구현

최소 힙

class MinHeap {
    ArrayList<Integer> heap;

    public MinHeap() {
        this.heap = new ArrayList<>();
        this.heap.add(0);
    }

    public void insert(int data) {
        heap.add(data); // 먼저 데이터 삽입
        int cur = heap.size() - 1; // 방금 전에 들어간 데이터의 인덱스
        while (cur > 1 && heap.get(cur / 2) > heap.get(cur)) { // 부모의 값이 더 클때
            int parentVal = heap.get(cur / 2);
            heap.set(cur / 2, data); //부모에는 방금 데이터를
            heap.set(cur, parentVal); //자식에게는 부모의 값을

            cur /= 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 cur = 1;
        while (true) {
            int leftIdx = cur * 2;
            int rightIdx = cur * 2 + 1;
            int targetIdx = -1;
            if (rightIdx < heap.size()) { // rightIdx가 heap.size보다 크면 오른쪽 자식 노드가 없는 상황
                targetIdx = heap.get(leftIdx) < heap.get(rightIdx) ? leftIdx : rightIdx;
            } else if (leftIdx < heap.size()) { // 자식 노드가 1개인 상황
                targetIdx = cur * 2; // or leftIdx
            } else { //부모노드 1개이거나, 비교할 자식 노드가 없을 경우
                break;
            }
            if (heap.get(cur) < heap.get(targetIdx)) { // 자식 노드 데이터가 클 경우는 break;
                break;
            } else { // 아닐경우 교체
                int parentVal = heap.get(cur);
                heap.set(cur, heap.get(targetIdx));
                heap.set(targetIdx, parentVal);
                cur = targetIdx; // 자리 교체후 idx 를 자식 노드 idx로 반환 후 다시 비교
            }
        }
            return target;
    }

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

최대 힙

class MaxHeap {
    ArrayList<Integer> heap;

    public MaxHeap() {
        this.heap = new ArrayList<>();
        this.heap.add(0);
    }

    public void insert(int data) {
        heap.add(data); // 먼저 데이터 삽입
        int cur = heap.size() - 1; // 방금 전에 들어간 데이터의 인덱스
        while (cur > 1 && heap.get(cur / 2) < heap.get(cur)) { // 부모의 값이 더 작을 때
            int parentVal = heap.get(cur / 2);
            heap.set(cur / 2, data); //부모에는 방금 데이터를
            heap.set(cur, parentVal); //자식에게는 부모의 값을

            cur /= 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 cur = 1;
        while (true) {
            int leftIdx = cur * 2;
            int rightIdx = cur * 2 + 1;
            int targetIdx = -1;
            if (rightIdx < heap.size()) { // rightIdx가 heap.size보다 크면 오른쪽 자식 노드가 없는 상황
                targetIdx = heap.get(leftIdx) > heap.get(rightIdx) ? leftIdx : rightIdx; // 더 큰 쪽을 선택
            } else if (leftIdx < heap.size()) { // 자식 노드가 1개인 상황
                targetIdx = cur * 2; // or leftIdx
            } else { //부모노드 1개이거나, 비교할 자식 노드가 없을 경우
                break;
            }
            if (heap.get(cur) > heap.get(targetIdx)) { // 부모 노드가 클 경우 break;
                break;
            } else { // 아닐경우 교체
                int parentVal = heap.get(cur);
                heap.set(cur, heap.get(targetIdx));
                heap.set(targetIdx, parentVal);
                cur = targetIdx; // 자리 교체후 idx 를 자식 노드 idx로 반환 후 다시 비교
            }
        }
        return target;
    }

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