힙

힙

개요

• 완전 이진 트리 형태
  • 마지막 레벨을 제외하고 모든 노드가 채워져 있는 것
  • 마지막 레벨은 좌측부터 채워져야 함
• 중복 값 허용
• 반 정렬 상태
  • 형제 노드간의 크기 우선 순위는 없음
• 최소값 또는 최대값을 빠르게 찾아내는데 유용한 자료구조
• 최소힙, 최대힙

---

최소 힙 (Min Heap)

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

최대 힙 (Max Heap)

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

---

삽입, 삭제

최소힙-삽입

• 트리의 가장 끝 위치에 데이터 삽입
• 부모 노드와 키 비교한 후 작을 경우 부모 자리와 교체(반복)
  

최소힙-삭제

• 최상위 노드 반환 및 삭제
• 가장 마지막 위치의 노드를 최상위 노드로 위치시킴
• 자식 노드 중 작은 값과 비교 후 부모 노드가 더 크면 자리 교체(반복)
  

---

최소힙 소스코드

힙은 완전이진트리이기 때문에 데이터의 연속성이 보장되어 배열로 만들 수 있다

// 비선형자료구조 - 힙
// ArrayList 로 최소 힙 구현

import java.util.ArrayList;

class MinHeap{
    ArrayList<Integer> heap;

    public MinHeap() {
        this.heap = new ArrayList<>();
        this.heap.add(0);   //인덱스 1부터 시작하기 위해 dummy data로 0을 미리 넣어놓음
    }


    //데이터를 힙에 추가하는 메소드
    public void insert(int data) {
        // 가장 끝 위치에 데이터 추가
        heap.add(data);

        // 추가한 후 부모와 크기 비교하며 자기 자리 찾아가기
        int cur = heap.size() - 1;  //방금 넣은 데이터의 인덱스 위치
        
        while (cur > 1 && heap.get(cur / 2) > heap.get(cur)) {  
            //cur이 1이면 루트 노드이기 때문에 더 비교할 필요가 없음
            //cur/2는 부모 노드, 부모 노드의 값이 삽입한 값보다 크면 위치 변경
            int parentVal = heap.get(cur / 2);  //부모 노드의 값을 잠깐 parentVal에 잠깐 담는다
            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;
        }
        
        // delete 대상 노드는 가장 상위 노드
        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()) { // 자식 노드 둘다 있는 경우
                //targetIdx는 leftIdx와 rightIdx 중 작은 값을 가지고 있는 것의 인덱스
                targetIdx = heap.get(leftIdx) < heap.get(rightIdx) ? leftIdx : rightIdx;
            } else if (leftIdx < heap.size()) { // 왼쪽 자식 노드만 있는 경우
                targetIdx = cur * 2;    //targetIdx는 자식 노드의 인덱스
            } else {
                break;
            }

            if (heap.get(cur) < heap.get(targetIdx)) {  // 부모가 자식 노드보다 작으면 종료
                break;
            } else {    // 부모가 더 크면 자리 바꾸기
                int parentVal = heap.get(cur);
                heap.set(cur, heap.get(targetIdx));
                heap.set(targetIdx, parentVal);
                cur = targetIdx;    //cur을 자식 노드의 인덱스로 바꿔서 반복문을 이어나감
            }
        }

        return target;
    }

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

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();
    }
}