[자바] 힙(Heap) - 최대힙 / 최소힙 개념과 구현. java

힙(Heap)

• 완전 이진트리의 형태를 갖는다.
  • 완전 이진트리는 마지막 레벨을 제외하고 모든 레벨의 노드가 꽉 차있다. 다만, 마지막 레벨의 노드는 왼쪽부터 채워져야한다. 가령 사진에서 마지막 레벨의 노드가 오른쪽에 붙어있다면 완전 이진트리가 아니게된다.
  • 포화 이진트리는 모든 레벨에서 노드가 차있는 경우를 말한다.

• 이진탐색트리와는 반대로 중복 값을 허용한다.
• 최소 힙은 부모노드가 자식노드보다 작은 값을 가지며, 최대 힙은 그 반대이다. 따라서 루트노드 값이 최댓값 혹은 최솟값이다.
• 형제노드간 크기 차이는 고려하지 않는 반 정렬 상태다.
• 최솟값이나 최댓값을 찾아내는데 유용한 자료구조이다.

 

최소 힙에서 삽입

• 트리의 가장 아래쪽에 데이터를 삽입한다.
• 만약 부모노드보다 키 값이 작다면 부모노드와 위치 교체를 반복하며 위로 올라간다.

 

최소 힙에서 삭제

1. 루트노드 값을 삭제 및 반환한다.
2. 가장 아래쪽 끝에 위치한 노드를 루트노드로 이동시킨다.
3. 루트노드의 자식노드 중 가장 작은 값이 루트노드보다 작다면 둘의 위치를 교체한다.
4. 3번 과정을 반복하며 부모노드와 자식노드값을 비교하면서 더 작은값을 아래로 내린다. 

 

최소 힙 구현

 

최소힙 - 삽입

왼쪽부터 채워지는 완전 이진트리 형태이기 때문에 배열의 연속성이 보장된다. 따라서 ArrayList로 구현이 가능하다.

import java.util.ArrayList;

class MinHeap {
    ArrayList<Integer> heap;

    public MinHeap() {
        this.heap = new ArrayList<>();
        this.heap.add(0);
    }	// 첫번째 데이터가 index 1부터 트리의 데이터가 채워질 수 있도록 index 0을 더미데이터로 채워넣는다.

    public void insert(int data) { // 데이터를 삽입할 때마다 부모노드와 값을 비교하며 위치를 바꿔주는 메서드 생성
        heap.add(data); // ArrayList 특성상 가장 끝에 데이터가 들어간다.
        int cur = heap.size() - 1; // cur은 heap.add한 data의 index 위치가 된다.
				   //ex) 네번째로 넣은 데이터의 위치는 5-1 = 4
        while (cur > 1 && heap.get(cur / 2) > heap.get(cur)) { // cur가 0이면 더미데이터이므로 반복문을 멈춘다.
            int parentVal = heap.get(cur / 2);  // (cur / 2)는 cur의 부모 위치가 된다.
            					// ex) cur가 7일때 부모의 위치는 3이다.
            heap.set(cur / 2, data);    // 부모값이 cur값보다 크다면 cur와 부모의 위치를 바꿔준다.
            heap.set(cur, parentVal); // cur위치에 부모값을 넣어준다.

            cur /= 2;
            // 삽입된 데이터의 위치를 나타내는 cur 값을 2로 나눠가며 부모노드와 자식노드 값 비교를 반복한다.
        }
    }

    public void printTree() { // 출력 메서드 생성
        for (int i = 1; i < this.heap.size(); i++) { // 더미데이터가 들어있는 index 0은 제외하고 출력
            System.out.print(this.heap.get(i) + " ");
        }
        System.out.println();
    }

        MinHeap minHeap = new MinHeap();
        minHeap.insert(30);
        minHeap.insert(40);
        minHeap.insert(10);

값이 삽입된 후 부모노드와의 크기를 비교하여 30과 10의 위치를 바꿔준 모습이다.

계속해서 삽입해보겠다.

        MinHeap minHeap = new MinHeap();

        minHeap.insert(50);
        minHeap.insert(60);
        minHeap.insert(70);
        minHeap.insert(20);       
        minHeap.insert(30);

 

최소힙 - 삭제

이번에는 삭제 및 반환 부분을 구현해보겠다.

public Integer delete() { // ArrayList 특성상 트리의 최상단 값이 삭제되므로 data는 받지않는다.
        if (heap.size() == 1) { // 더미데이터
            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가 노드의 사이즈를 벗어나면 cur의 오른쪽 자식노드는 없다.
                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)) {  // 현재 노드값이 자식노드보다 작으므로 탈출
                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++) { // 더미데이터가 들어있는 index 0은 제외하고 출력
        System.out.print(this.heap.get(i) + " ");
    }
    System.out.println();
}

System.out.println(minHeap.delete());

위에서 설명한 개념대로 코드를 구현했다. 그에 맞춰서 사진처럼 노드 삭제 및 반환, 자리교체까지 모두 이루어진 것을 볼 수 있다.

 

 

최대 힙 구현

기본적으로 최소힙과 구현 방식은 같다. 다만, 부모노드와 자식노드를 비교하는 부분에서 최소힙과 부등호를 반대로 작성해주면 된다.

최대힙 - 삽입 및 삭제

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)) { //부모노드(cur/2)가 더 작을때 위치를 바꿔준다.
            int parentVal = heap.get(cur / 2);
            heap.set(cur / 2, data);
            heap.set(cur, parentVal);

            cur /= 2;
        }
    }

    public Integer delete() {
        if (heap.size() == 1) {
            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()) {
                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)) {  // 현재 노드값이 자식노드보다 크므로 탈출(최소힙과 반대)
                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(this.heap.get(i) + " ");
        }
        System.out.println();
    }

        MaxHeap maxHeap = new MaxHeap();
        
        maxHeap.insert(30);
        maxHeap.insert(40);
        maxHeap.insert(10);
        maxHeap.insert(50);
        maxHeap.insert(60);
        maxHeap.insert(70);
        maxHeap.insert(20);
        maxHeap.insert(30);

        System.out.println(maxHeap.delete());
        maxHeap.printTree();

 

 

여기까지 힙의 개념 및 최대힙, 최소힙의 삽입과 삭제를 구현해보았다.