[자료구조] 힙(Heap)

1. 정의 🐳

  힙(Heap)이란 여러 값들 중 최댓값 혹은 최솟값을 빠르게 찾아내기 위한 자료구조이다. 

힙의 특징

• 완전 이진트리의 일종이다. 
• 반정렬 상태이다.
  최대힙(Max Heap) 또는 최소힙(Min Heap)에 따라서 루트 노드가 항상 가장 큰 값이거나 가장 작은 값을 유지하기 때문이다.
• 중복된 값을 허용한다.

힙의 종류

• 최대 힙 (Max Heap)
  부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리 형식
• 최소 힙 (Min Heap)
  부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리 형식

 

2. 동작 방식 🐟

인덱스	0	1	2	3	4	5	6	7	8
값	-	9	7	6	4	5	1	3	8

  Heap은 배열을 통해 쉽게 구현이 가능하다. 그 이유는 힙이 완전 이진트리이기 때문에 배열에 값을 순서대로 넣으면서 구현할 수 있기 때문이다. 

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

  인덱스 번호를 활용하여 '부모 노드와 자식 노드에 쉽게 접근할 수 있다. 위와 같은 쉬운 접근 방식을 위해 0번 인덱스는 사용하지 않는다. 

  Heap의 '삽입 방식'과 '삭제 방식'을 통해 힙의 동작 방식을 알아보자.

1. 삽입

  삽입은 다음과 같은 순서로 이루어진다.

1. 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
   배열의 마지막에 원소를 추가한다.
2. 새로운 노드를 부모 노드와 비교하면서 교환을 한다.
   최대 힙의 경우, 추가한 값이 부모 노드보다 크면 자리를 바꾼다.
   최소 힙의 경우, 추가한 값이 부모 노드보다 작으면 자리를 바꾼다.
3. 2번을 반복한다.

  최대 힙에서의 삽입을 그림을 통해 살펴보자.

  7번 인덱스까지 있는 최대힙에 8이라는 숫자를 삽입해 보자. 위의 동작방식과 아래의 그림의 흐름을 잘 따라간다면 이해를 하는데 큰 무리가 없을 거라고 생각한다.

  완성된 모습은 아래와 같다.

2. 삭제

  힙에서의 삭제는 루트 노드를 삭제하는 것이다. 만약 최대힙이라면 최댓값을 삭제하는 것이고 최소힙이라면 최솟값을 삭제하는 것이다. 방식은 아래와 같다.

1. 루트노드에서 값을 제거한다.
2. 마지막 노드를 루트 노드로 옮긴다.
3. 자식 노드와 대소관계를 비교한다.
   최대 힙의 경우, 자식 노드 중에서 더 큰 노드와 부모 노드의 자리를 바꾼다.
   최소 힙의 경우, 자식 노드 중에서 더 작은 노드와 부모 노드의 자리를 바꾼다.
4. 3번을 반복한다.

  최대힙에서의 삭제를 그림을 통해 살펴보자. 11번 인덱스까지 있는 최대힙에서 삭제가 이루어진다고 하자. 이것 또한 동작 방식과 그림의 흐름을 잘 따라간다면 이해를 하는데 큰 무리가 없을 거라고 생각된다.

  완성된 모습은 아래와 같다.

 

3. 구현(JAVA) 🐬

  삽입과 삭제에서의 동작 방식을 기반으로 코드를 살펴보자. 

1. 삽입

static void insert_max_heap(int x) {

    // 마지막 노드에 원소 x를 추가
    maxHeap[++heapSize] = x;

    for(int i = heapSize; i > 1; i /= 2) {

        // 자식노드가 부모노드보다 더 큰 경우 자리 교환
        if(maxHeap[i / 2]  < maxHeap[i]) {
            swap(i / 2, i);
        }
        else {
            break;
        }
    }
}

2. 삭제

static int delete_max_heap() {
    // 배열이 비어있는 경우
    if(heapSize == 0)
        return -1;

    //삭제할 노드 저장(리턴을 위한 것)
    int item = maxHeap[1];
    // 마지막 노드를 루트 노드로 옮긴다.
    maxHeap[1] = maxHeap[heapSize];
    maxHeap[heapSize--] = 0;

    for(int i = 1; i * 2 <= heapSize;) {
        // 마지막 노드가 자식 노드들보다 더 큰 경우
        if(maxHeap[i] > maxHeap[i * 2]
                && maxHeap[i] > maxHeap[i * 2 + 1]) {
            break;
        }
        // 왼쪽 노드가 더 큰 경우
        else if(maxHeap[i * 2] > maxHeap[i * 2 + 1]) {
            swap(i, i * 2);
            i = i * 2;
        }
        // 오른쪽 노드가 더 큰 경우
        else {
            swap(i, i * 2 + 1);
            i = i * 2 + 1;
        }
    }

    return item;
}

 

해당 글은
코드 연구소의 '[자료구조]Max Heap, Min Heap, Heap 이란? | C언어 Heap 구현',
Passwd님의 '최소 힙/ 최대 힙',
Gyoogle님의 '힙(Heap)'
을 참고하였습니다.