8. 힙

1. 힙

- 배열을 기반한 완전 이진 트리 형태의 자료구조

- 최대힙, 최소힙 두가지 종류가 있다

- 최대힙은 루트 노드 값이 자식들 보다 큰 힙을 말하고 최소힙은 반대 이다

- 최대힙 에서는 루트 노드 값이 가장 크기에 최대 값을 찾는 연산은 Big-O(1) 시간을 가진다

- 삽입, 삭제시에 heapify 과정을 거쳐야 해서 Big-O(logn)의 시간을 가진다

2. Max Heap ADT

- init(self)

- heap을 초기화 한다

- insert(self, data)

- 힙에 데이터를 부모 노드가 자식 노드 보다 큰 상태로 저장한다

- pop(self, data)

- 힙의 첫 요소(가장큰) 데이터를 반환하고 heapify 진행한다

- peek(self)

- 힙의 가장 큰 데이터를 반환한다.

- count(self)

- 힙의 데이터의 수를 반환한다. 

class MaxHeap:
    def __init__(self):
        self.list = [None]
        self.total = 0

    def insert(self, data):
        def _insert(index, data):
            if index == 1:
                return
            if self.list[index] > index // 2:
                self.list[index], self.list[index // 2] = self.list[index // 2], self.list[index]
            _insert(index // 2, data)
            return True

        if not self.total:
            self.list.append(data)
            self.total += 1
            return True
        self.list.append(data)
        self.total += 1
        is_insert = _insert(self.total, data)
        return is_insert

    def pop(self):
        def _delete(index):
            left_first = False
            if index * 2 + 1 > self.total:
                return True
            if self.list[index * 2] > self.list[index * 2 + 1]:
                left_first = True
            if self.list[index] < self.list[index * 2] and left_first:
                self.list[index], self.list[index * 2] = self.list[index * 2], self.list[index]
                index = index * 2
            else:
                self.list[index], self.list[index * 2 + 1] = self.list[index * 2 + 1], self.list[index]
                index = index * 2 + 1
            _delete(index)

        if not self.total:
            return False
        max_data = self.list[1]
        self.list[1] = self.list.pop()
        self.total -= 1
        _delete(1)
        return max_data

    def peek(self):
        return self.list[1]

    def count(self):
        return self.total


h = MaxHeap()
h.insert(1)
h.insert(2)
h.insert(3)
h.insert(4)
h.insert(7)
h.insert(9)
h.insert(8)
h.insert(21)
h.insert(44)
print(h.list)
print(f'count :{h.count()}')
print(f'pop: {h.pop()}')
print(h.list)
print(f'peek : {h.peek()}')
print(f'pop: {h.pop()}')
print(h.list)
print(f'pop: {h.pop()}')
print(h.list)

-------------------------
[None, 44, 21, 9, 8, 3, 2, 7, 1, 4]
count :9
pop: 44
[None, 21, 8, 9, 4, 3, 2, 7, 1]
peek : 21
pop: 21
[None, 9, 8, 7, 4, 3, 2, 1]
pop: 9
[None, 8, 4, 7, 1, 3, 2]