힙(Heap)과 완전 이진 트리(Complete binary tree)

Complete binary tree

 

단 두개의 자식 노드만 갖는 "이진 트리"중 노드가 왼쪽부터 차례대로 채워져 있는 트리를 말한다.

왼쪽은 완전 이진 트리, 오른쪽은 단순 이진 트리

위 그림의 왼쪽은 왼쪽부터 차례대로 채워져 있으므로 완전 이진 트리이다.

(3번 노드의 자식 노드 두개가 모두 채워질 경우 "포화 이진 트리"가 된다.)

 

오른쪽은 2번 노드의 왼쪽 자식 노드가 비어있고 오른쪽 자식 노드가 채워져 있으므로

 

완전 이진 트리를 만족하지 못한다.

 

Heap

 

개발자 채용 필기 테스트에 단골로 나오는 자료구조이므로 잘 알아두자.

 

최소 힙을 기준으로 부모 노드가 항상 자식 노드보다 작은 형태의 "완전 이진 트리"를 말한다.

 

보통 배열로 간단하게 구할 수 있다. 배열로 구현시 (부모 노드 인덱스 = 자식 노드 인덱스 / 2)

 

(왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2) (오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2 + 1)

 

로 인덱싱을 쉽게 할 수 있다.

 

우선 순위 큐(priopriority queue)의 구현시 가장 많이 쓰는 구조가 바로 Heap이다.

 

최소 힙의 조건에 의해 root 노드는 항상 전체 노드중 가장 작은 값이 위치하게 된다.

 

삽입, 삭제만 알면 간단히 구현할 수 있다.

 

삽입

현재 그림과 같은 Heap이 있다고 하자. Heap의 삽입은 먼저 가장 끝의 노드에 이루어진다.

 

여기에 "2"를 추가해 보자. 그럼 다음과 같이 추가가 될 것이다.

부모 노드는 항상 자식 노드 보다 작아야 한다. 현재 새로 추가된 2보다 부모 노드인 6이 더 크므로

 

최소 힙을 만족하지 못한다. 따라서, 둘이 swap을 해준다.

swap후 또 부모 노드를 보니 여전히 최소 힙을 만족하지 못한다. 다시 swap을 한다.

이제서야 최소 힙을 만족하는 형태가 되었다. 이처럼 삽입의 경우 가장 마지막 노드에 새 노드를 추가한 후

 

부모 노드 보다 커지거나 루트 노드가 될 때 까지 swap을 해준다.

 

비교 노드의 인덱스가 1/2씩 줄음으로 시간 복잡도는 O(logN) 이다.

 

삭제

힙의 삭제는 루트 노드에서 이뤄진다. 따라서 2가 pop되어 삭제가 되고 마지막 노드가 루트 노드가 된다.

삽입과 달리 이번에는 최소 힙을 만족 하기 위해 루트 노드로부터 자식 노드로 비교를 한다.

 

왼쪽 자식 노드 부터 확인하는데 마침 3이므로 swap한다.

다시 자식 노드를 확인 해 보니 7이므로 종료한다. 삽입과 동일한 과정을 반대로 할 뿐이므로

 

시간 복잡도는 O(lonN)이다.

 

Code

 

위 삽입, 삭제 기능만 잘 구현하면 된다.

#include <iostream>
using namespace std;

class Heap {
private:
	int* nodes;
	int size;
	int capacity;

public:
	Heap(int defaultCapacity) {
		this->capacity = defaultCapacity;
		this->size = 0;
		this->nodes = new int[this->capacity];
	}

	~Heap() {
		delete this->nodes;
	}

	void add(int data) {
		// 예외 발생( 크기 재할당을 해주어도 된다 )
		if (this->size >= this->capacity)
			throw this->size;

		// 배열로 구현 시 인덱스는 1부터 시작
		this->nodes[++this->size] = data;

		// 순위 조정
		int i = this->size;
		while (i > 1 && this->nodes[i] < this->nodes[i / 2]) {
			swap(i, i / 2);
			i /= 2;
		}
	}

	int pop() {
		// 예외 발생
		if (this->size == 0)
			throw this->size;

		// 첫번째 원소 반환 후 마지막 원소를 첫번째에 대입
		int ret = this->nodes[1];
		this->nodes[1] = this->nodes[this->size--];

		// 조정
		int i = 1;
		while (this->size >= (i * 2 + 1)) {
			if (this->nodes[i] > this->nodes[i * 2]) {
				swap(i, i * 2);
				i *= 2;
			}
			else if (this->nodes[i] > this->nodes[i * 2 + 1]) {
				swap(i, i * 2 + 1);
				i = i * 2 + 1;
			}
			else {
				break;
			}
		}

		return ret;
	}

	void printAll() {
		if (this->size == 0) {
			cout << "This heap has no element." << endl;
			return;
		}

		cout << "size : " << this->size << endl;
		for (int i = 1; i <= this->size; i++) {
			cout << this->nodes[i] << " ";
		}
		cout << endl;
	}

private:
	void swap(int idx1, int idx2) {
		int tmp = this->nodes[idx1];
		this->nodes[idx1] = this->nodes[idx2];
		this->nodes[idx2] = tmp;
	}
};