자료구조 - 힙(Heap)

자료구조 - 힙(Heap)

---

1. 힙

•  중복값을 허용하며 반 정렬상태인 완전 이진트리
• 최솟값이나 최댓값을 찾을 때 유용

 

2. 최소힙, 최대힙

• 최소힙(Min Heap)
  부모 노드 키 <= 자식 노드 키
• 최대힙(Max Heap)
  부모 노드 키 >= 자식 노드 키
• 최소힙 - 삽입
  - 트리의 젤 끝에 데이터 삽입후 삽입한 데이터 < 부모 노드의 키 이면 자리 교체 반복
• 최소힙 - 삭제
  - 루트 노드를 반환 및 삭제 후 가장 마지막 노드로 변경
  - 변경한 노드와 자식 노드를 비교하며 부모노드 > 자식 노드이면 자리 교체 반복

 

2. 최소힙 삽입, 삭제 구현

- 리스트로 트리를 만들어 부모와 자식노드의 값을 비교해 자리를 바꾸어주면 되어 비교적 쉽게 구현하였다.

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

import java.util.ArrayList;
// heap을 리스트 형태로 만들어서 사용
class MinHeap{
    ArrayList<Integer> heap;
    MinHeap(){
        this.heap = new ArrayList<>();
        this.heap.add(0);
    }
    // 데이터 삽입
    public void insert(int data){
        this.heap.add(data);
        // 자식노드 < 부모노드 일때 자리교체
        int cur = this.heap.size() - 1;
        while (cur > 1 && this.heap.get(cur) < this.heap.get(cur / 2)){
            int parentData = this.heap.get(cur/2);
            this.heap.set(cur, parentData);
            this.heap.set(cur / 2, data);

            cur = cur / 2;
        }
    }

    // 데이터 삭제 및 반환
    public Integer delete(){
        if (this.heap.size() < 2){
            System.out.println("heap is empty");
            return null;
        }
        // 루트 노드 키를 마지막 노드 키로 변경 후 마지막 노드 삭제
        int target = this.heap.get(1);
        this.heap.set(1, this.heap.get(this.heap.size()-1));
        this.heap.remove(this.heap.size() - 1);
        // idx 1부터 반복하며 부모 노드 > 자식 노드이면 변경
        int curIdx = 1;
        int targetIdx;
        while (true){
            int leftIdx = curIdx * 2;
            int rightIdx = curIdx *2 + 1;
            // 왼쪽 자식과 오른쪽 자식 중 값이 더 작은 쪽을 타겟인덱스로 선정
            if (rightIdx < this.heap.size()){
                targetIdx = this.heap.get(leftIdx) > this.heap.get(rightIdx) ? rightIdx : leftIdx;
            } else if (leftIdx < this.heap.size()) {
                targetIdx = leftIdx;
            } else {
                break;
            }

            if (this.heap.get(targetIdx) < this.heap.get(curIdx)){
                int curData = this.heap.get(curIdx);
                this.heap.set(curIdx, this.heap.get(targetIdx));
                this.heap.set(targetIdx, curData);
            }
            curIdx = 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();
    }
}

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

 

3. 최대힙 삽입, 삭제 구현

- 최소힙 구현에서 부등호의 방향만 바꾸어 주면 된다.

import java.util.ArrayList;

// Practice 1
// ArrayList 로 최대 힙 구현
class MaxHeap{
    ArrayList<Integer> heap;
    MaxHeap(){
        this.heap = new ArrayList<>();
        this.heap.add(0);
    }
    // 데이터 삽입
    public void insert(int data){
        this.heap.add(data);
        // 자식노드 > 부모노드 일때 자리교체
        int cur = this.heap.size() - 1;
        // Min Heap와 다르게 부등호만 반대로 수정
        while (cur > 1 && this.heap.get(cur) > this.heap.get(cur / 2)){
            int parentData = this.heap.get(cur/2);
            this.heap.set(cur, parentData);
            this.heap.set(cur / 2, data);

            cur = cur / 2;
        }
    }

    // 데이터 삭제 및 반환
    public Integer delete(){
        if (this.heap.size() < 2){
            System.out.println("heap is empty");
            return null;
        }
        // 루트 노드 키를 마지막 노드 키로 변경 후 마지막 노드 삭제
        int target = this.heap.get(1);
        this.heap.set(1, this.heap.get(this.heap.size()-1));
        this.heap.remove(this.heap.size() - 1);
        // idx 1부터 반복하며 부모 노드 < 자식 노드이면 변경
        int curIdx = 1;
        int targetIdx;
        while (true){
            int leftIdx = curIdx * 2;
            int rightIdx = curIdx *2 + 1;
            // 왼쪽 자식과 오른쪽 자식 중 값이 더 큰 쪽을 타겟인덱스로 선정
            if (rightIdx < this.heap.size()){
                // 여기 부등호도 수정
                targetIdx = this.heap.get(leftIdx) < this.heap.get(rightIdx) ? rightIdx : leftIdx;
            } else if (leftIdx < this.heap.size()) {
                targetIdx = leftIdx;
            } else {
                break;
            }

            // 여기 부등호도 수정
            if (this.heap.get(targetIdx) > this.heap.get(curIdx)){
                int curData = this.heap.get(curIdx);
                this.heap.set(curIdx, this.heap.get(targetIdx));
                this.heap.set(targetIdx, curData);
            }
            curIdx = 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();
    }
}

public class Practice1 {
    public static void main(String[] args) {
        // Test code
        MaxHeap maxHeap = new MaxHeap();
        System.out.println("== 데이터 삽입 ==");
        maxHeap.insert(30);
        maxHeap.insert(40);
        maxHeap.insert(10);
        maxHeap.printTree();
        maxHeap.insert(50);
        maxHeap.insert(60);
        maxHeap.insert(70);
        maxHeap.printTree();
        maxHeap.insert(20);
        maxHeap.printTree();
        maxHeap.insert(30);
        maxHeap.printTree();

        System.out.println();
        System.out.println("== 데이터 삭제 ==");
        System.out.println("삭제: " + maxHeap.delete());
        maxHeap.printTree();
        System.out.println("삭제: " + maxHeap.delete());
        maxHeap.printTree();
        System.out.println("삭제: " + maxHeap.delete());
        maxHeap.printTree();
    }
}

 

4. 최소힙, 최대힙을 이용한 오름차순, 내림차순

- 처음에는 힙은 같은 레벨에서는 정렬을 하지 않는데 어떻게 정렬이 되나 라는 생각을 했다.

힙의 delete를 이용해서 최소힙일 경우 가장 작은 값이 루트로 오게하여 오름차순을 나타내고,

최대합일 경우 가장 큰 값이 루트로 오게하여 내림차순을 나타낸다.

// 힙의 delete를 이용해서 최소힙일 경우 가장 작은 값이 루트로 오게하여 오름차순을 나타내고
// 최대합일 경우 가장 큰 값이 루트로 오게하여 내림차순을 나타낸다.
public class Practice2 {
    public static void solution(MinHeap minHeap) {
        MaxHeap maxHeap = new MaxHeap();
        System.out.println("== 오름차순 ==");
        while (minHeap.heap.size() != 1){
            int key = minHeap.delete();
            System.out.print(key + " ");
            maxHeap.insert(key);
        }
        System.out.println();

        System.out.println("== 내림차순 ==");
        while (maxHeap.heap.size() != 1){
            System.out.print(maxHeap.delete() + " ");
        }
    }

    public static void main(String[] args) {
        // Test code
        MinHeap minHeap = new MinHeap();
        minHeap.insert(30);
        minHeap.insert(40);
        minHeap.insert(10);
        minHeap.insert(50);
        minHeap.insert(60);
        minHeap.insert(70);
        minHeap.insert(20);
        minHeap.insert(30);

        solution(minHeap);
    }
}