02_heap

heap은 비선형 자료구조이다. 가장 큰 값이나 가장 작은값이 항상 첫번째로 들어가게 한다. sorted와는 다르게 이진트리 방식으로 구성되어 있는것이 특징. 

 

 

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:
            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] 가 출력되어야 합니다!

다음은 maxheap을 파이썬 모듈이 아닌 직접 구현해본 모습이다! 

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):
        # 구현해보세요!
        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[left_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]
            cur_index = max_index


        return prev_max  # 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]

밑은 구현한 힙에서 지우는 과정이다

 

크게 어렵진 않았는데 일반적으로 정렬해주는 sort말고 이런구조를 사용하는게 더 괜찮은 경우가 있을 거 같단 생각이 들었다.