8-4. [C/C++] 힙에서의 삽입 연산

아래 글 내용에서 이어지는 내용이므로 아래 글을 보고 오는 것을 추천한다.

https://seongmoahn.tistory.com/107

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

힙에서의 삽입 연산

힙에 새로운 요소가 들어오면, 일단 완전 이진트리의 조건을 만족하는 마지막 위치에 삽입한다.

그러면 대부분의 경우 힙 트리의 조건을 만족하지 않을 것이다.

그래서 삽입 후에 부모 노드와 비교하며 조건의 맞는 자리를 찾는다.

---

삽입 연산의 구현

삽입 연산의 알고리즘을 알아보자.

insert(key) // 최대 힙에서의 삽입 알고리즘

heapSize <- heapSize + 1;
i <- heapSize;
node[i] <- key;
while i != 1 and node[i] > node[PARENT(i)] do
	node[i] <-> node[PARENT(i)];
    i <- PARENT(i);

위 알고리즘에서는 <-> 기호가 노드를 교환하는 것을 나타낸다.

하지만 실제 구현에서는 매번 노드를 교환하는 것이 아닌, 이동 횟수를 줄이기 위해 부모 노드만을 끌어내린 다음에 삽입될 위치가 정해지면 그 위치에 새로운 노드를 이동시키는 방식으로 구현한다.

 

앞서 만들어놨던 기본 틀에 insert() 연산을 추가하자.

// MaxHeap.h
#include "HeapNode.h"
#define MAX_ELEMENT 200
...
class MaxHeap {
    HeapNode node[MAX_ELEMENT];
    int size;

public:
...
	void insert(int key) {
        if (isFull()) errorPrint("Heap Overflow");

        int i = ++size;
        while (i != 1 && key > getParent(i).getKey()) {
            node[i] = getParent(i);
            i /= 2;
        }
        node[i].setKey(key);
    }
...
};

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