8-3. [C/C++] 힙(Heap) 구현

힙이란?

힙은 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다.

힙을 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 큰/작은 완전 이진 트리이다.

이진 탐색 트리와 달리 힙 트리는 중복된 값을 허용한다.

 

앞에서 힙은 반 정렬의 상태를 유지한다고 했었다.

(최대)힙은 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도의 느슨한 정렬 상태를 유지한다.

힙의 목적이 삭제 연산에서 가장 큰/작은 값을 효율적으로 찾아내기만 하면 되는 것이기 때문에 전체 요소들을 정렬할 필요는 없다.

왼쪽 그림과 같이 부모 노드의 키 값이 자식 노드의 키 값보다 큰 경우를 최대 힙(max heap)이라고 부른다.

오른쪽 그림과 같이 부모 노드의 키 값이 자식 노드의 키 값보다 작은 경우를 최소 힙(min heap)이라고 부른다.

• 최대 힙(max heap) : KEY(부모 노드) >= KEY(자식 노드)
• 최소 힙(min heap) : KEY(부모 노드) <= KEY(자식 노드)

---

힙의 구현 방법

힙은 완전 이진트리이기 때문에 중간에 비어 있는 요소가 없다.

그래서 각 노드에 번호를 순차적으로 부여할 수가 있고, 이 번호를 배열의 인덱스로 사용하면 노드들을 효율적으로 관리할 수 있다.

 

배열로 이진트리를 구현했을 때의 장점이 궁금하다면 아래 글을 참고하자.

https://seongmoahn.tistory.com/94

6-3. 이진 트리의 구현 방법

• 노드 i 의 부모 노드 인덱스 : i / 2
• 노드 i 의 왼쪽 자식 노드 인덱스 : 2 * i
• 노드 i 의 오른쪽 자식 노드 인덱스 : 2 * i + 1

앞서 다뤘던 추상 자료형을 바탕으로 힙 클래스의 UML 다이어그램을 구성해보자.

위 다이어그램을 바탕으로 힙에서 사용할 정수를 저장하는 노드 클래스와 최대 힙 클래스의 기본 틀을 만들자.

// HeapNode.h
#include <iostream>
using namespace std;

class HeapNode {
    int key;
    
public:
    HeapNode(int key = 0) : key(key) {}

    void setKey(int key) { this->key = key; }
    int getKey() { return key; }

    void display() { cout << "[" << key << "]"; }
};

아래 최대 힙 클래스 메소드 중 insert()와 remove()는 구현되어 있지 않다.

삽입/삭제 연산에 대해 알아본 뒤 두 연산의 코드를 채워보자.

// MaxHeap.h
#include "HeapNode.h"
#define MAX_ELEMENT 200

inline void errorPrint(const char *message) { cout << message << endl; exit(1); }

class MaxHeap {
    HeapNode node[MAX_ELEMENT];
    int size;

public:
    MaxHeap() : size(0) {}

    bool isEmpty() { return size == 0; }
    bool isFull() { return size == (MAX_ELEMENT - 1); }

    HeapNode getParent(int idx) { return node[idx / 2]; }
    HeapNode getLeftChild(int idx) { return node[idx * 2]; }
    HeapNode getRightChild(int idx) { return node[idx * 2 + 1]; }

    // void insert(int key) {...}

    // HeapNode remove() {...}

    HeapNode find() { return node[1]; }

    void display() {
        cout << "Heap 내용";
        for (int i = 1, level = 1; i <= size; i++) {
            if (i == level) {
                cout << endl;
                level *= 2;
            }
            node[i].display();
        }
        cout << endl << endl;
    }
};

위 코드는 아래 이미지를 클릭해 깃허브에서도 확인할 수 있다.