힙(Heap)

힙(Heap)

완전 이진 트리 형태

- 중복 값 허용
- 반 정렬 상태

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

 

힙의 종류

 

• 최대 힙

부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
key(부모 노드) >= key(자식 노드)

• 최소 힙

부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
key(부모 노드) <= key(자식 노드)

 

 

힙을 구현하기 앞서

 

힙을 저장하는 표준적인 자료구조는 배열 이다.
구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.

힙에서의 부모 노드와 자식 노드의 관계

 

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

 

최소 힙(Min Heap)
부모 노드의 키가 자식 노드의 키보다 작거나 같은 형태

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

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

 

최대 힙(Max Heap)
부모 노드의 키가 자식 노드의 키보다 크거나 같은 형태

 

최소 / 최대 힙 구현(ArrayList) 

import java.util.ArrayList;
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; // 방금 들어온 data의 인덱스 위치
        // while (cur > 1 && heap.get(cur / 2) < heap.get(cur)) Max heap 부등호 교체
        while (cur > 1 && heap.get(cur / 2) > heap.get(cur)){ // 방금 들어온 data가 부모 data 보다 작다면
            int parentVal = heap.get(cur / 2);
            heap.set(cur / 2, data); // 부모 자리에 추가한 data 할당
            heap.set(cur , parentVal); // 맨 끝 자식 자리에 부모 data 할당 (위치 바꿔주기)

            cur /= 2; // 2로 나눠서 그 위에 부모랑 다시 비교
        }
    }
    public Integer delete(){ // 최상위 노드를 먼저 삭제하는 거니 data는 받을 필요가 없다.
        if(heap.size() == 1){ // size가 1이면 더미 데이터 하나만 있는 것
            System.out.println("Heaep is empty!");
            return null;
        }
        int target = heap.get(1); // 최상위 노드

        heap.set(1, heap.get(heap.size() - 1)); // 최상위 노드에 마지막 data 삽입
        heap.remove(heap.size() - 1); // 마지막 data를 최상위에 배치했으니 삭제

        int cur = 1; // 최상위 노드 위치

        while (true){
            int leftIdx = cur * 2; // 왼 쪽 자식 노드
            int rightIdx = cur * 2 + 1; // 오른쪽 자식 노드
            int targetIdx = -1;

            if(rightIdx < heap.size()){  // heap 사이즈 보다 작아야 오른쪽 자식 노드가 있는 것,
            	// targetIdx = heap.get(leftIdx) > heap.get(rightIdx) Max heap 부등호 교체
                targetIdx = heap.get(leftIdx) < heap.get(rightIdx) ? leftIdx : rightIdx; // 왼쪽 자식 노드가 작다면 왼쪽 자식노드
            } else if (leftIdx < heap.size()) {  // 자식 노드가 하나인 경우
                targetIdx = leftIdx;
            }else { // 자식 노드가 없는 상황
                break;
            }
            // if(heap.get(cur) < heap.get(targetIdx)) Max heap 부등호 교체
            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;
            }
        }
            return target;
    }

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

public static void main(String[ ] args)

 

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