[자료구조] 이진 트리의 꽃, 힙에 대해 알아보자

 

📚 힙 정의

힙은 데이터에서 최댓값과 최솟값을 찾기 위해 고안된 완전 이진 트리이다.

 

힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조이다.

즉 부모 노드의 값이 자식 노드의 값보다 항상 커야 한다.

그러면 가장 큰 값이 모든 자식보다 크기 때문에 가장 위로 간다.

바로 루트 노드로 말이다.

 

 

루트 노드인 9가 모든 노드보다 크다

 

이렇게 아래로 갈수록 작고 위로 갈수록 커지는 힙은 Max Heap이라 하고

이와 반대인 경우는 Min Heap이라 한다.

 

 

 

그런데 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있어야 하는 규칙이 있다.

 

 

🤔 그러면 힙에 새로운 노드를 삽입하거나 이미 존재하는 노드를 삭제할 때

규칙을 어기지 않게 하려면 어떻게 해야 할까?

 

 

 지금부터 노드 삽입과 노드 삭제 과정을 훑어보자

📖 노드 삽입

 

이 힙은 MinHeap의 삽입과정을 다룬 것이다. 

1. 원소를 맨 마지막에 넣는다.
2. 부모 노드와 비교한다. 만약 크다면 자리를 바꾼다.
3. 부모 노드보다 작거나 루트 노드에 도달하지 않을 때까지 2. 과정을 반복한다.

 

 

📝 노드 삽입 코드(feat : python)

 

class MaxHeap:
    def __init__(self):
        self.items = [None]

    def insert(self, value):
        self.items.append(value)
        aryLen = len(self.items)
        if aryLen < 3 : return
        compareIndex = aryLen - 1

        while 1 < compareIndex:

            if self.items[compareIndex] < self.items[compareIndex // 2]: break
            self.items[compareIndex], self.items[compareIndex // 2] = self.items[compareIndex // 2] , self.items[compareIndex]
            compareIndex = compareIndex // 2



max_heap = MaxHeap()
max_heap.insert(3)
max_heap.insert(4)
max_heap.insert(2)
max_heap.insert(9)
print(max_heap.items)  # [None, 9, 4, 2, 3] 가 출력되어야 합니다!

 

⏱ 힙의 노드 삽입의 시간복잡도

 

 

여기서 우리는 노드 삽입에 담당하는 insert함수의 시간 복잡도를 알아봐야 한다.

 

이진트리의 최대 높이는 O(log(N))이다

insert 함수 안에 while 반복문은 최대 트리의 높이만큼 반복된다.

그러므로 insert함수의 시간복잡도는 O(log(N)) 이다.

 

📖 노드 삭제

 

이 힙은 MinHeap의 삭제과정을 다룬 것이다. 

 

MaxHeap의 삭제 과정을 다음과 같다.

 

 

노드 삭제는 오로지 루트 노드만 제거할 수 있다.

또한 원소를 삭제할 때도 힙의 규칙이 지켜져야 한다.

노드 삭제 방법은 다음과 같다.

 

1. 루트 노드와 맨 끝에 있는 원소를 교체한다.
2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제한다.
3. 변경된 노드와 자식 노드들을 비교한다.
두 자식 중 더 큰 자식과 비교해서 더 크다면 자리를 바꾼다.
4. 자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때까지 3. 과정을 반복한다.
5. 2에서 제거한 원래 루트 노드를 반환한다.

 

 

📝 노드 삽입 코드(feat : python)

 

class MaxHeap:
    def __init__(self):
        self.items = [None]

    def insert(self, value):
        self.items.append(value)
        cur_index = len(self.items) - 1

        while cur_index > 1:  # cur_index 가 1이 되면 정상을 찍은거라 다른 것과 비교 안하셔도 됩니다!
            parent_index = cur_index // 2
            if self.items[parent_index] < self.items[cur_index]:
                self.items[parent_index], self.items[cur_index] = self.items[cur_index], self.items[parent_index]
                cur_index = parent_index
            else:
                break

    # 1. 루트 노드와 맨 끝에 있는 원소를 교체한다.
    # 2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제한다. 이 때, 끝에 반환해줘야 하니까 저장한다.
    # 3. 변경된 노드와 지식 노드들을 비교합니다. 두 자식 중 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리를 바꾼다.
    # 4. 자식 노드들 보다 부모 노드가 더 크거나 가장 바닥에 도달하지 않을때까지 3. 을 반복한다.
    # 5. 2에서 제거한 원래 루트 노드를 반환한다.
    def delete(self):
        aryLen = len(self.items)
        # 2.
        delete_node = self.items[1]
        # 1.
        self.items[1] = self.items[aryLen - 1]
        del self.items[aryLen - 1]
        compareIndex = 1

        # 3. 4.
        while compareIndex < aryLen:

            if self.items[compareIndex * 2] < self.items[compareIndex * 2 + 1] and self.items[compareIndex] < self.items[compareIndex * 2 + 1]:
                self.items[compareIndex] , self.items[compareIndex * 2 + 1] = self.items[compareIndex * 2 + 1] , self.items[compareIndex]

            elif self.items[compareIndex * 2 + 1] < self.items[compareIndex * 2] and self.items[compareIndex] < self.items[compareIndex * 2]:
                self.items[compareIndex], self.items[compareIndex * 2] = self.items[compareIndex * 2], self.items[compareIndex]
            else : break
        # 5.
        return delete_node  # 8 을 반환해야 합니다.


max_heap = MaxHeap()
max_heap.insert(8)
max_heap.insert(6)
max_heap.insert(7)
max_heap.insert(2)
max_heap.insert(5)
max_heap.insert(4)
print(max_heap.items)  # [None, 8, 6, 7, 2, 5, 4]
print(max_heap.delete())  # 8 을 반환해야 합니다!
print(max_heap.items)  # [None, 7, 6, 4, 2, 5]

 

 

⏱ 힙의 노드 삽입의 시간복잡도

 

삭제 과정의 시간복잡도 또한 O(log(N))이다.

반복문이 최대 완전 이진트리의 최대 높이만큼 반복되기 때문이다.