비선형 자료구조 - 힙(Heap)

힙(Heap)

• 항상 완전 이진 트리 형태 (트리가 마지막 레벨을 제외하고 모든 레벨에서 완전히 채워져 있으며, 마지막 레벨에서는 가능한 한 왼쪽부터 채워지는 것을 의미)
  • 중복 값 허용
  • 반 정렬 상태
• 최소값 또는 최대값을 빠르게 찾아내는데 유용한 자료구조
  • 최소 힙, 최대 힙

 

 

시간 복잡도

• 삽입(Insertion): O(log n)
• 삭제(Deletion): O(log n)
• 최대값/최소값 접근(Peek): O(1)

 

 

힙 속성(Heap Property)

• 최대 힙(Max Heap)
  • 부모 노드의 값이 자식 노드의 값보다 크거나 같은 구조 (형제 노드(같은 레벨)는 크기 상관X, 중복 값 역시 상관X)
  • 루트 노드에는 가장 큰 값이 위치

** 루트(Root) ** : 트리 구조에서 최상위 노드를 의미

계층적인 데이터 구조로, 노드(Node)들이 부모-자식 관계로 연결

루트 노드는 부모가 없는 유일한 노드이며, 트리의 시작점이자 가장 중요한 노드

 

 

• 최소 힙(Min Heap)
  • 부모 노드의 값이 자식 노드의 값보다 작거나 같은 구조 (형제 노드(같은 레벨)끼리는 크기 상관X)
  • 루트 노드에는 가장 작은 값이 위치

 

 

주요 연산

1. 삽입(Insertion):
   • 새로운 요소를 힙에 추가할 때는 트리의 가장 마지막 위치에 삽입한 후, 힙 속성을 유지하기 위해 부모 노드와 비교하여 필요시 위치를 교환하는 작업인 힙-업(Heapify Up)을 진행
2. 삭제(Deletion):
   • 일반적으로 루트 노드를 제거
   • 루트 노드를 제거한 후, 마지막 노드를 루트 위치로 이동시키고, 자식 노드와 비교하여 힙 속성을 유지하기 위해 힙-다운(Heapify Down)을 수행
3. 최대값/최소값 추출:
   • 최대 힙에서는 루트 노드에 최대값이, 최소 힙에서는 최소값이 위치하므로, 힙에서 최댓값 또는 최솟값을 빠르게 추출할 수 있음
   • 이 연산은 O(1) 시간에 가능

 

ex) 최소 힙 - 삽입

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

 

1. 트리의 가장 마지막 위치에 삽입한 후
2. 최소 힙은 부모 노드의 키 값이 자신보다 작아야 하므로 자신의 부모 노드와 비교하여 추가된 데이터가 작으면 자리를 교체

 

 

ex) 최소 힙 - 삭제

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

 

1. 루트 노드를 제거한 후
2. 마지막 노드를 루트 위치로 이동시키고
3. 루트 노드(삽입된 노드)부터 양쪽 자식 노드들과 비교하여 더 작은 자식 노드와 자리 교체(반복)

 

 

 

구현 코드

Java- ArrayList로 최소 힙 구현

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

import java.util.ArrayList;

class MinHeap {
    ArrayList<Integer> heap;

    // 생성자
    public MinHeap() {
        // 객체 생성
        this.heap = new ArrayList<>();
        this.heap.add(0); // 더미 데이터를 삽입하여 1번 인덱스부터 시작할 수 있도록 설정
    }

    // 데이터 삽입 메소드
    public void insert(int data) {
        heap.add(data);

        // 부모 노드와 비교
        int cur = heap.size() - 1; // 추가한 데이터의 idx
        while (cur > 1 && heap.get(cur / 2) > heap.get(cur)) { // heap.get(cur / 2) => 자기 자신의 부모 idx
            int parentVal = heap.get(cur / 2); // 부모 값 임시 보관
            heap.set(cur / 2, data); // 부모 데이터에 추가한 데이터 넣기
            heap.set(cur, parentVal); // cur 인덱스에 부모의 값 넣기

            // 위로 이동한 후 다시 체크
            cur /= 2;
        }
    }

    public Integer delete() {
        if (heap.size() == 1) { // (heap.size() == 1 => 더미 데이터만 존재
            System.out.println("Heap is empty!");
            return null;
        }

        int target = heap.get(1); // root node꺼냄: heap 기준 더미 데이터 제외 제외하면 1이 root node

        heap.set(1, heap.get(heap.size() - 1)); // 1번 위치에 마지막 데이터 넣기
        heap.remove(heap.size() - 1); // 마지막 데이터 옮겼으니 삭제 처리

        // 추가 데이터가 MinHeap에 부합하는지 확인
        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 = cur * 2;
            } 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() {
        // 더미 데이터 제외 출력을 위해 i는 1부터
        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
        MaxHeap minHeap = new MaxHeap();
        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();
    }
}

== 데이터 삽입 ==
40 30 10
70 50 60 30 40 10
70 50 60 30 40 10 20
70 50 60 30 40 10 20 30

== 데이터 삭제 ==
삭제: 70
60 50 30 30 40 10 20
삭제: 60
50 40 30 30 20 10
삭제: 50
40 30 30 10 20 

 

Java- ArrayList로 최대 힙 구현

// Practice 1
// ArrayList 로 최대 힙 구현
import java.util.ArrayList;

class MaxHeap {
    ArrayList<Integer> heap;

    // 생성자
    public MaxHeap() {
        // 객체 생성
        this.heap = new ArrayList<>();
        this.heap.add(0); // 더미 데이터를 삽입하여 1번 인덱스부터 시작할 수 있도록 설정
    }

    // 데이터 삽입 메소드
    public void insert(int data) {
        heap.add(data);

        // 부모 노드와 비교
        int cur = heap.size() - 1; // 추가한 데이터의 idx
        while (cur > 1 && heap.get(cur / 2) < heap.get(cur)) { // heap.get(cur / 2) => 자기 자신의 부모 idx
            int parentVal = heap.get(cur / 2); // 부모 값 임시 보관
            heap.set(cur / 2, data); // 부모 데이터에 추가한 데이터 넣기
            heap.set(cur, parentVal); // cur 인덱스에 부모의 값 넣기

            // 위로 이동한 후 다시 체크
            cur /= 2;
        }
    }

    public Integer delete() {
        if (heap.size() == 1) { // (heap.size() == 1 => 더미 데이터만 존재
            System.out.println("Heap is empty!");
            return null;
        }

        int target = heap.get(1); // root node꺼냄: heap 기준 더미 데이터 제외 제외하면 1이 root node

        heap.set(1, heap.get(heap.size() - 1)); // 1번 위치에 마지막 데이터 넣기
        heap.remove(heap.size() - 1); // 마지막 데이터 옮겼으니 삭제 처리

        // 추가 데이터가 MinHeap에 부합하는지 확인
        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 = cur * 2;
            } 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() {
        // 더미 데이터 제외 출력을 위해 i는 1부터
        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();
    }
}

== 데이터 삽입 ==
40 30 10
70 50 60 30 40 10
70 50 60 30 40 10 20
70 50 60 30 40 10 20 30

== 데이터 삭제 ==
삭제: 70
60 50 30 30 40 10 20
삭제: 60
50 40 30 30 20 10
삭제: 50
40 30 30 10 20