자료구조 4주차_힙

자료구조 4주차_힙

---

힙(Heap)이란?

테이터에서 최댓값과 최소값을 빠르게 찾기 위해

고안된 완전 이진 트리

 

heap, [출처 : 스파르타 코딩 클럽]

 

📌 Max Heap 원소 추가

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

    def insert(self, value):
        # 1. 새노드를 맨 끝에 추가한다.
        # 2. 지금 넣은 새노드를 부모와 비교한다. 만약 부모보다 크다면, 교체한다.
        # 3. 이 과정을 꼭대기까지 반복한다.
        self.items.append(value)
        cur_index = len(self.items) - 1 # 가장 마지막에 넣은 value의 idx

        while cur_index > 1:
            parent_index = cur_index // 2
            if self.items[cur_index] > self.items[parent_index]:
                self.items[cur_index], self.items[parent_index] = self.items[parent_index], self.items[cur_index]
                cur_index = parent_index
            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] 가 출력되어야 합니다!

현재 인덱스가 1이 되면 종료. 즉, 가장 끝(Root Node)에 도달하면 종료!

 

완전 이진트리의 최대 높이는 O(log(N))
그러면, 원소를 추가할 때 Root Node 까지 가기위해 반복하는 최대 횟수도 O(log(N)) 
즉! 맥스 힙의 원소 추가는  O(log(N))의 시간 복잡도를 가진다고 분석할 수 있음.

---

📌 Max Heap 원소 제거

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

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

        cur_index = 1
        while cur_index <= len(self.items) - 1:
            left_child_index = cur_index * 2
            right_child_index = cur_index * 2 + 1
            max_index = cur_index

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

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

            if max_index == cur_index:
                break

            self.items[cur_index], self.items[max_index] = self.items[max_index], self.items[cur_index]
        return prev_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]

 

 

left_child_index <= len(self.items) - 1
right_child_index <= len(self.items) - 1

left, right 자식 노드가 존재하는 지 여부 점검.

인덱스는 0부터 시작하므로. len(self.items)-1 해야줘야 한다.

 

맥스 힙의 원소 삭제 또한 마찬가지로 O(log(N)) 만큼의 시간 복잡도를 가진다.

---

원소 최댓값을 빠르게 삭제하거나 추가할 때 사용하면 좋은 자료구조!