[자료구조/알고리즘] 힙(Heap)

힙(Heap)

• 정의
  - 완전 이진 트리 형태의 중복 값을 허용하는 자료구조(배열의 연속성이 보장됨)
• 특징
  - 중복 값을 허용
  - 반 정렬 상태

최소 힙(Min Heap)

• 부모 노드의 값이 자식 노드의 값보다 작거나 같은 형태
• 형제 노드들은 값에 의해 위치 우선순위가 정해져있지 않음(반 정렬상태)
  

최대 힙(Max Heap)

• 부모 노드의 값이 자식 노드의 값보다 작거나 같은 형태
• 형제 노드들은 값에 의해 위치 우선순위가 정해져있지 않음(반 정렬상태)
  

데이터 삽입

• 트리의 가장 끝 위치에 데이터 삽입
• 부모 노드의 값과 비교한 후 규칙에 따라 부모 노드의 값과 교체를 반복

데이터 삭제

• 루트 노드를 반환 및 삭제
• 가작 맞막 위치의 노드를 최상위 노드로 위치 시킴
• 자식 노드의 값과 비교 후 규칙에 따라 부모 노드의 값과 교체를 반복

구현

부모와 자식 노드간 값 비교 부분의 부등호만 서로 반대

• 최소 힙

class MinHeap {
    ArrayList<Integer> heap;

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

    public void insert(int data) {
        this.heap.add(data);

        int curIdx = heap.size() - 1;
        while (curIdx > 1 && this.heap.get(curIdx / 2) > this.heap.get(curIdx)) {
            int parent = this.heap.get(curIdx / 2);
            this.heap.set(curIdx / 2, data);
            this.heap.set(curIdx, parent);

            curIdx /= 2;
        }
    }

    public Integer delete() {
        if (this.heap.size() == 1) {
            System.out.println("The matrix is already empty");
            return null;
        }

        int tar = this.heap.get(1);
        int lastIdx = heap.size() - 1;

        this.heap.set(1, this.heap.get(lastIdx));
        this.heap.remove(lastIdx);

        int curIdx = 1;
        while (true) {
            int leftIdx = curIdx * 2;
            int rightIdx = curIdx * 2 + 1;
            int tarIdx = -1;

            if (rightIdx < heap.size()) {
                tarIdx = this.heap.get(leftIdx) < this.heap.get(rightIdx) ? leftIdx : rightIdx;
            } else if (leftIdx < heap.size()) {
                tarIdx = leftIdx;
            } else {
                break;
            }

            if (this.heap.get(curIdx) < this.heap.get(tarIdx)) {
                break;
            } else {
                int parent = this.heap.get(curIdx);
                this.heap.set(curIdx, this.heap.get(tarIdx));
                this.heap.set(tarIdx, parent);
                curIdx = tarIdx;
            }
        }

        return tar;
    }

    public void print() {
        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) {
        MinHeap minHeap = new MinHeap();

        minHeap.insert(30);
        minHeap.insert(40);
        minHeap.insert(10);
        minHeap.print();
        minHeap.insert(50);
        minHeap.insert(60);
        minHeap.insert(70);
        minHeap.print();
        minHeap.insert(20);
        minHeap.insert(30);
        minHeap.print();

        System.out.println("===== 삭제 =====");
        System.out.println("삭제: " + minHeap.delete());
        minHeap.print();
        System.out.println("삭제: " + minHeap.delete());
        minHeap.print();
    }
}

• 최대 힙

class MaxHeap {
    ArrayList<Integer> heap;

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

    public void insert(int data) {
        this.heap.add(data);

        int curIdx = heap.size() - 1;
        while (curIdx > 1 && this.heap.get(curIdx / 2) < this.heap.get(curIdx)) {
            int parent = this.heap.get(curIdx / 2);
            this.heap.set(curIdx / 2, data);
            this.heap.set(curIdx, parent);

            curIdx /= 2;
        }
    }

    public Integer delete() {
        if (this.heap.size() == 1) {
            System.out.println("The matrix is already empty");
            return null;
        }

        int tar = this.heap.get(1);
        int lastIdx = heap.size() - 1;

        this.heap.set(1, this.heap.get(lastIdx));
        this.heap.remove(lastIdx);

        int curIdx = 1;
        while (true) {
            int leftIdx = curIdx * 2;
            int rightIdx = curIdx * 2 + 1;
            int tarIdx = -1;

            if (rightIdx < heap.size()) {
                tarIdx = this.heap.get(leftIdx) > this.heap.get(rightIdx) ? leftIdx : rightIdx;
            } else if (leftIdx < heap.size()) {
                tarIdx = leftIdx;
            } else {
                break;
            }

            if (this.heap.get(curIdx) > this.heap.get(tarIdx)) {
                break;
            } else {
                int parent = this.heap.get(curIdx);
                this.heap.set(curIdx, this.heap.get(tarIdx));
                this.heap.set(tarIdx, parent);
                curIdx = tarIdx;
            }
        }

        return tar;
    }

    public void print() {
        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) {
        MaxHeap maxHeap = new MaxHeap();

        maxHeap.insert(30);
        maxHeap.insert(40);
        maxHeap.insert(10);
        maxHeap.print();
        maxHeap.insert(50);
        maxHeap.insert(60);
        maxHeap.insert(70);
        maxHeap.print();
        maxHeap.insert(20);
        maxHeap.insert(30);
        maxHeap.print();

        System.out.println("===== 삭제 =====");
        System.out.println("삭제: " + maxHeap.delete());
        maxHeap.print();
        System.out.println("삭제: " + maxHeap.delete());
        maxHeap.print();
    }
}