자료구조 알고리즘 힙이란 무엇인가?

힙이란 무엇인가?

힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

 

항상 최대의 값들이 필요한 연산이 있다면? 바로 힙을 쓰면 되겠죠!

그러면 힙을 구현하려면 어떻게 해야할까요?

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

다시 말하면 부모 노드의 값이 자식 노드의 값보다 항상 커야 합니다.

그러면 가장 큰 값은 모든 자식보다 커야 하기 때문에 가장 위로 가겠죠!

따라서 최대의 값들을 빠르게 구할 수 있게 되는 것입니다.

 

참고로, 힙은 다음과 같이 최대값을 맨 위로 올릴수도 있고, 최솟값을 맨 위로 올릴 수도 있습니다! 최댓값이 맨 위인 힙을 Max 힙, 최솟값이 맨 위인 힙을 Min 힙이라고 합니다!

 

맥스힙에 원소 추가!

힙의 규칙 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있어야 합니다. 은 항상 지켜져야 합니다. 따라서, 원소를 추가하거나 삭제할때도 위의 규칙이 지켜져야 합니다!

 

코드로 보기!!!

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

    def insert(self, value):
        self.items.append(value)
        curr_idx = len(self.items)-1
        while curr_idx > 1 :
            parent_idx = curr_idx // 2
            if self.items[curr_idx] > self.items[parent_idx] :
                self.items[curr_idx], self.items[parent_idx] = self.items[parent_idx], self.items[curr_idx]
                curr_idx = parent_idx
            else:
                break
        return


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] 가 출력

 

 

맥스힙에 원소 삭제!

최대 힙에서 원소를 삭제하는 방법은 최댓값, 루트 노드를 삭제하는 것입니다!

스택과 같이 맨 위에 있는 원소만 제거할 수 있고, 다른 위치의 노드를 삭제할 수는 없습니다!

 

코드로 보기!!

def delete(self):

        self.items[1], self.items[-1] = self.items[-1], self.items[1]
        max = self.items.pop()

        curr_idx = 1

        while curr_idx <= len(self.items) -1 :
            left_child = curr_idx * 2
            right_child = curr_idx * 2 + 1
            max_idx = curr_idx

            if left_child <= len(self.items) - 1 and self.items[left_child] > self.items[max_idx]:
                max_idx = left_child

            if right_child <= len(self.items) - 1 and self.items[right_child] > self.items[max_idx]:
                max_idx = right_child

            if max_idx == curr_idx:
                break

            self.items[curr_idx], self.items[max_idx] = self.items[max_idx], self.items[curr_idx]
            curr_idx = max_idx
        return max


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)) 만큼의 시간 복잡도를 가진다고 분석할 수 있습니다.