Heap의 개념

힙은 트리의 일종인데, "complete tree"이거나 "nearly complete tree"이어야 한다. 그리고 다음 두 가지 종류로 나뉜다.

max-heap의 경우 각 노드의 key 값이 자식 노드들의 key 값보다 크거나 같고, min-heap의 경우 각 노드의 key 값은 자식 노드들의 key 값보다 작거나 같아야 한다.

Heap의 특성

max-heap을 기준으로 살펴보자. 힙의 root는 트리에서 가장 큰 값을 갖고 있으며, root의 왼쪽/오른쪽 서브트리도 같은 특성을 유지한다. 만약 min-heap이라면 힙의 root가 트리에서 가장 작은 값을 갖게 된다.

구현은 주로 linked list보다는 array로 이루어진다.

노드와 자식 간의 관계는 다음과 같이 확인할 수 있다.

index가 i인 노드를 생각해본다면,

1. • i번째 노드 왼쪽 자식: 2i+1
   • i번째 노드 오른쪽 자식: 2i+2
   • i번째 노드의 부모 노드: floor((i-2)/2)
   • j번째 노드가 왼쪽 자식이면, 오른쪽 자식은 j+1

Heap의 연산

Heap에서 자료를 추가하거나 삭제할 수 있으며, 순회, 검색, 출력과 같은 기능도 작동하게 할 수 있다.

다만 힙은 위에서 언급한, root의 key 값이 가장 크거나 (max-heap) 작아야 (min-heap) 하고 그 특성이 모든 서브트리에 대해서도 동일하게 유지되어야 하며, 정의했던 것처럼 (nearly) complete tree라는 특성도 유지해야 한다.

만약 노드를 추가하거나 삭제를 한 후 그냥 가만히 둔다면 힙의 정의를 만족하지 못할 것이다.

따라서 우리는 Reheap up / Reheap down 이라는 함수를 정의해서 heap의 모양을 유지하도록 한다.

수도코드의 경우, 순회, 검색, 출력 자체는 기존 트리에서 구현하는 것과 동일하므로 건너뛰고, 삽입 및 삭제의 경우는 각각 함수의 뒷부분에서 Reheap up, Reheap down함수를 불러오기만 하면 되므로 건너뛰도록 하겠다. 여기에서는 Reheap Up 및 Reheap Down에 대해서만 소개하도록 하겠다.

Reheap Up

삽입 연산을 수행하면서 같이 불러와야 하는 함수로 가장 마지막에 삽입된 요소를 위쪽으로 이동시키면서 올바른 위치에 갈 수 있게 한다. 삽입 자체는 가장 첫 번째 빈 leaf node에 들어가기 때문에 heap의 구조를 유지하기 위해서는 node를 이동시켜주어야 한다.

삽입된 노드의 부모 노드와 key 값을 비교하여, 만약 삽입된 노드가 부모 노드의 key 값보다 크면 서로 위치를 교환한다. 이 과정을 계속 반복하여 heap의 구조를 유지시킨다.

수도코드는 다음과 같다.

void reheapUp (HEAP *heap, NODE *newNode) {
	if (newNode != root) {
		parent = parent->newNode;
		if (newNode->key > parent->key) {
			swap(newNode, parent);
			reheapUp(heap,parent);
		}
	}
}

Reheap Down

heap은 nearly complete tree이므로 root을 바로 삭제하게 되면, heap의 구조가 유지되지 못한다. 따라서 last tree node의 값을 root로 옮긴 후, root를 아래로 이동시켜서 heap의 배열 특성(heap-ordering property)이 충족되도록 위치를 변경해야한다.

root 노드를 삭제할 때, 그냥 삭제하게 되면 heap의 구조가 붕괴되므로, 자식 노드 중 오른쪽 노드와 값을 교환해가며 heap 구조의 마지막 노드로 이동시킨 후 삭제한다.

수도코드는 다음과 같다.

void reheapDown (HEAP *heap, NODE *root, int last) {
	if (root->left) {
		int leftKey = root->left->key;
		if (root->right) {
			int rightKey = root->right->key;
		}
		else {
			int rightKey = NULL;
		}
	}
	if (leftKey > rightKey) {
		largeSubtree = root->left;
	}
	else {
		largeSubtree = root->right;
	}
	if (root->key < largeSubtree->key) {
		swap(root, largeSubtree);
		reheapDown(heap, largeSubtree, last);
	}
}

class & self

class(클래스)란, 데이터와 기능이 함께 묶여 있는 하나의 틀이다. 이 틀을 이용하여 여러 개의 object(객체)를 만들 수 있다. 각각의 객체는 독립적이어서 서로에게 영향을 주지 않는다.

이해하기 쉽게 예를 들어 보자.

클래스는 초콜릿을 만드는 틀과 같다. 녹은 초콜릿을 틀에 부어 초콜릿을 무한정 생산할 수 있다. 이 틀로 만들어진 각각의 초콜릿을 객체라고 생각하면 된다.

각각의 초콜릿은 독립적이므로 초콜릿에 어떤 데코레이션을 올리더라도 다른 초콜릿에는 영향을 주지 않는다.

클래스를 이용하면 같은 기능을 하는 독립적인 여러 객체를 생성할 수 있기 때문에 편리하다. 일기장 프로그램을 작성해야 하는데, 사람마다 다른 일기장을 만들어줄 때 이걸 일일이 코드로 작성하면 시간낭비, 그리고 자원낭비(!)이기 때문이다.

클래스와 객체는 다음과 같이 생성할 수 있다.

class chocoMaker:
	pass
    
a = chocoMaker() # a 객체 생성
b = chocoMaker() # b 객체 생성

아직 chocoMaker라는 클래스에 아무 값이나 기능이 포함되어있지 않다.

클래스에 함수를 포함시키는 방법은 다음과 같다.

class chocoMaker:
    def decorate(self, color, type):
    	self.color = color
        self.type = type
        
a = chocoMaker()
a.decorate('white', 'sprinkle')

클래스 내부의 함수는 method(메서드)라고 부른다.

메서드의 첫 번째 매개변수는 대개 self를 쓴다. self의 역할은 객체 자기 자신을 호출하는 것이다.

객체를 생성하고 메서드를 사용할 때는 위와 같이 객체.메서드(...) 이런 식으로 작성해야 한다. 그런데 첫 번째 매개변수였던 self는 실제로 사용할 때 입력하지 않아도 된다. 객체.메서드(...)에서 객체가 self로 자동으로 전달되기 때문이다.

만약 이 방법이 마음에 들지 않는다면 아래와 같이 작성해도 된다.

a = chocoMaker()
chocoMaker.decorate(a, 'white', 'sprinkle')

decorate 메서드의 수행문을 살펴보자.

a.decorate('white', 'sprinkle')과 같이 작성하면, a라는 객체 내부에 color, type 객체변수가 생성되고, 'white', 'sprinkle'값이 저장된다.

클래스로 만든 여러 가지 객체 간엔 독립성이 보장되므로, 한 객체의 객체변수의 값을 수정했다고 하여 다른 객체의 객체변수 값이 달라지지 않는다.

init/생성자

chocoMaker 클래스에 다른 메서드도 추가해보자.

class chocoMaker:
    def decorate(self, color, type):
    	self.color = color
        self.type = type
    def plate(self):
    	res = self.color + self.type
        return res

plate 메서드를 추가하였다. 이 상황에서 다음과 같이 코드를 작성하면 오류가 발생한다.

b = chocoMaker()
b.plate()

이유는 앞서 만들어두었던 decorate 메서드를 거치지 않고는 plate 메서드를 실행할 수 없기 때문이다.

하지만 decorate 수행 후 plate를 수행하도록 하면 불편하다. 한 번에 해결할 수 있는 방법이 없을까?

우리는 이럴 때 생성자(constructor)를 사용한다. 생성자는 객체를 생성할 때 자동으로 호출되는 메서드를 의미한다. __init__으로 사용할 수 있다.

다음 코드를 살펴보자.

class chocoMaker:
    def __init__(self, color, type):
        self.color = color
        self.type = type
    def decorate(self, color, type):
    	self.color = color
        self.type = type
    def plate(self):
    	res = self.color + self.type
        return res

c = chocoMaker('pink', 'decopen')

c라는 객체를 만들 때, decorate를 불러올 필요 없이 chocoMaker와 함께 원하는 값을 전달할 수 있다.

상속

코드를 짜다 보면 같은 속성을 갖는 새로운 클래스를 생성해야 할 필요가 있다.

예를 들어, 색깔과 데코레이션의 종류만을 갖는 chocoMaker 클래스에서 데코레이션의 개수를 추가한 클래스를 새로 만드는 경우를 생각해보자.

새로운 클래스를 생성하는 것보다 기존의 chocoMaker 클래스를 이용하여 만드는 편이 훨씬 간단하다. 이럴 때 이용하는 것이 super().__init__를 이용한 상속이다.

class superChocoMaker(chocoMaker):
    def __init__(self, color, type, num): # num 추가
        super().__init__(color, type)
        self.num = num
        
    def superPlate(self): # 기존 클래스의 메서드를 상속
        super().plate()

클래스를 생성할 때 클래스 옆 괄호 안에 상속할 클래스의 이름을 적어둔 다음, super().__init__의 input으로 상속할 기존 클래스의 요소의 이름을 적어준다.

때로는 새로 만든 클래스에서 기존의 메서드와 같은 이름을 사용하지만 다른 기능을 하는 메서드를 만들고 싶을 수 있다. 그럴 때에는 그냥 상속받은 (새로 만든) 클래스 내부에서 메서드를 다시 정의하면 된다.

기존 클래스의 메서드를 상속받고 싶을 때는 super().메서드와 같은 방식으로 작성한다.