힙

힙은 부모가 자식보다 큰 완전 이진트리.

힙은 좌,우 자식의 위치가 대소관계를 반영하지않음 (BST와는 다름)

계산편의를 위해 인덱스는 1부터사용

• Parent : x / left : 2x / right : 2x+1

---

힙의 규칙

힙은 항상 큰 값이 상위 레벨 작은값이 하위레벨에 있어야함

---

최대힙 - 삽입 시간 복잡도

• 결국 원소를 맨 밑에 넣어서 꼭대기까지 올림 -> 완전 이진트리의 최대 높이는 O(log(N))즉 반복하는 최대횟수도 O(log(N))이다

• 맥스 힙의 원소추가는 O(log(N))의 시간복잡도를 가짐

---

최대 힙 - 추출 알고리즘

• 최댓값, 루트 노드를 삭제 하는것 스택과 같이 맨 위에 있는 원소만 제거할 수 있고, 다른 위치의 노드를 삭제할수는 없다.
  • 방법
    1. 루트 노드와 맨 끝에 있는 원소를 교체
    2. 맨 뒤에 있는 원소를 삭제
    3. 변경된 노드와 자식노드들을 비교 두 자식 중 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리를 바꿉니다.
    4. 자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때까지 3. 과정을 반복합니다.
    5. b에서 제거한 원래 루트 노드를 반환합니다.

---

추출 시간 복잡도

• 결국 원소를 맨 위에 올려서 바닥까지 비교하면서 내리고 있습니다.
• ->완전 이진트리의 최대 높이는 O(log(N)) 이라고 말씀 드렸었죠!
  그러면, 반복하는 최대 횟수도 O(log(N)) 입니다.

즉! 맥스 힙의 원소 삭제는 O(log(N)) 만큼의 시간 복잡도를 가진다고 분석할 수 있습니다.

---

구현

class BinaryHeap(object):
    def __init__(self):
        self.items=[None]
    def __len__(self):
        return len(self.items)-1
    def _percolate_up(self):
        i=len(self)
        parent=i//2
        while parent>0:
            if self.items[i]<self.items[parent]:
                self.items[i],self.items[parent]=\
                self.items[parent], self.items[i]
            i=parent
            parent=i//2
        return
    def insert(self,k):
        self.items.append(k)
        self._percolate_up()
    def _percolate_down(self,idx):
        left = 2*idx
        right = 2*idx+1
        smallest = idx
        if left<=len(self) and self.items[left]<self.items[smallest]: # 루트가 왼쪽보다 크다면
            smllest=left
        if right <= len(self) and self.items[right] < self.items[smallest]: # 루트가 오른쪽보다 크다면
            smllest = right

        if smallest != idx: # 바껴야한다면
            self.items[smallest],self.items[idx]= \
                self.items[idx], self.items[smallest]
            self._percolate_down(smallest)
        return
    def extract(self):
        extracted = self.items[1]
        self.items[1]=self.items[len(self)] # 마지막이랑 루트 랑 바꿔주는거
        self.items.pop()# 마지막 버려주고
        self._percolate_down(1)
        return extracted