[Algorithms] Min Heap, Max Heap

학교 과제 하면서 짰다

C++ 클래스, 상속 사용하면서 짜니까 재밌다

 

처음에 min heap의 pop 메소드를 짤 때 왼쪽 자식부터 확인하면서 자식에 부모보다 큰 값이 저장되어 있으면 값을 바꾸고 바로 다음 level로 넘어갔는데 그렇게 하니까 틀렸다.

만약 3 -> {2, 1}이 저장되어 있을 때 왼쪽 자식이랑만 값을 비교하면 2 -> {3, 1} 상태가 된다.

(a -> {b, c}는 부모노드, 왼쪽 자식, 오른족 자식에 저장된 값이 각각 a, b, c라는 의미이다)

이는 부모 노드의 값은 자식 노드의 값보다 작거나 같아야 한다는 원칙을 위반한다.

 

위와 같은 상황에서 두 자식 노드에 대해 모두 비교하면 되지 않을까? 라는 생각을 했지만

만약 그렇게 한다면 3 -> {2, 1} 상태에서 2 -> {3, 1} 상태가 되고, 또 비교해서  1 -> {3, 2} 상태가 된다.

모든 자식 노드가 값이 업데이트 되기 때문에, 그것들 모두 각자의 자식 노드와 비교하는 과정이 필요하다.

이렇게 되면 최악의 경우 확인해야 하는 내용이 2의 거듭제곱의 형태로 증가한다.

그러므로 부모 노드의 값을 두 자식노드 중 작은 값을 갖는 것이랑만 확인하는 것이 가장 효율적이다.

 

max heap에서는 그 반대로 자식 노드 중 큰 값을 부모 노드와 비교해야 하고.

#include <iostream>
#include <vector>
#include <algorithm>
#define ENDL '\n'
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

template<typename T>
class Heap {
public:
	Heap<T>() {
		end = 1;
		tree.resize(1);
	}

	virtual void push(T value) = 0;
	virtual void pop() = 0;

	T top() {
		return tree[1];
	}

	bool empty() {
		return end == 1;
	}

	ull size() {
		return end;
	}

	void printAll(ostream& out) {
		vector<T> tempTree = tree;
		int tempEnd = end;

		while (!empty()) {
			out << top() << ' ';
			pop();
		}
		out << ENDL;

		end = tempEnd;
		for (int i = 1; i < end; i++) {
			tree[i] = tempTree[i];
		}
	}

protected:
	vector<T> tree;
	ull end;
};

template<typename T>
class MinHeap : public Heap<T> {
public:
	virtual void push(T value) {
		if (this->end == this->tree.size()) {
			this->tree.resize(this->tree.size() * 2);
		}
		this->tree[this->end++] = value;

		for (ull child = this->end - 1; child >= 1; child /= 2) {
			ull parent = child / 2;
			if (parent >= 1 && this->tree[parent] > this->tree[child]) {
				swap(this->tree[parent], this->tree[child]);
			}
			else {
				break;
			}
		}
	}

	virtual void pop() {
		this->tree[1] = this->tree[this->end - 1];
		this->end--;

		for (ull parent = 1; parent * 2 < this->end; ) {
			ull smallerChild;
			if (parent * 2 + 1 < this->end) {
				smallerChild = parent * 2 + (this->tree[parent * 2] < this->tree[parent * 2 + 1] ? 0 : 1);
			}
			else {
				smallerChild = parent * 2;
			}

			if (this->tree[smallerChild] < this->tree[parent]) {
				swap(this->tree[parent], this->tree[smallerChild]);
				parent = smallerChild;
			}
			else {
				break;
			}
		}
	}
};

template<typename T>
class MaxHeap : public Heap<T> {
public:
	virtual void push(T value) {
		if (this->end == this->tree.size()) {
			this->tree.resize(this->tree.size() * 2);
		}
		this->tree[this->end++] = value;

		for (ull child = this->end - 1; child >= 1; child /= 2) {
			ull parent = child / 2;
			if (parent >= 1 && this->tree[parent] < this->tree[child]) {
				swap(this->tree[parent], this->tree[child]);
			}
			else {
				break;
			}
		}
	}

	virtual void pop() {
		this->tree[1] = this->tree[this->end - 1];
		this->end--;

		for (ull parent = 1; parent * 2 < this->end; ) {
			ull largerChild;
			if (parent * 2 + 1 < this->end) {
				largerChild = parent * 2 + (this->tree[parent * 2] > this->tree[parent * 2 + 1] ? 0 : 1);
			}
			else {
				largerChild = parent * 2;
			}

			if (this->tree[largerChild] > this->tree[parent]) {
				swap(this->tree[parent], this->tree[largerChild]);
				parent = largerChild;
			}
			else {
				break;
			}
		}
	}
};

확실히 재밌다.

컴공 오길 정말 잘 했다는 생각이 든다.

코딩하다가 종종 스트레스 받을 때는

내가 하고 있는 일 그 자체가 이유가 아니라

마감 시간으로부터의 압박 때문인 경우가 많은 거 같다.

확실히

재밌다