프로그래머스 강의_22

힙(Heaps)

이진트리의 한 종류(이진 힙-binary heap)
1. 루트(root)노드가 언제나 최댓값 또는 최솟값을 가진다.
최대 힙(max heap), 최소 힙(min heap)

2. 완전 이진 트리여야 함

최대 힙(Max Heap)의 예

재귀적으로도 정의됨 => 어느 노드를 루트로 하는 서브트리도 모두 최대 힙 , 느슨한 정렬 구조를 가지고 있다.

이진 탐색 트리와의 비교

1. 원소들은 완전히 크기 순으로 정렬되어있는가?
2. 특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가?
3. 부가의 제약 조건은 어떤 것인가?
   힙은 완전 이진 트리여야함.

최대 힙(Max Heap)의 추상적 자료구조

연산의 정의

• init() : 빈 최대 힙을 생성
• insert(item) : 새로운 원소를 삽입
• remove() : 최대 원소 (root node)를 반환 그리고 동시에 이 노드를 삭제한다.

데이터 표현의 설계

배열을 이용한 이진 트리의 표현
노드 번호 m을 기준으로
==> 왼쪽 자식의 번호 2 m
==> 오른쪽 자식의 번호 2 m + 1
==> 부모 노드의 번호 m // 2
====> 완전 이진트리이므로 노드의 추가/삭제는 마지막 노드에서만

코드의 구현 - 빈 힙 생성

class MaxHeap:
    def __init(self):
        self.data = [None]

최대 힙에 원소 삽입

1. 트리의 마지막 자리에 새로운 원소를 임시로 저장
2. 부모 노드와 키 값을 비교하여 크기가 크다면 위로, 위로, 이동
3. 12의 자식이 30이되면 안되기 때문에 성질을 만족하도록 위로 이동시킨다. 30과 12의 자리 교체, 30과 부모 노드값을 비교하면 30이 20보다 크므로 30을 root node자리로 가게된다.

최대 햅에 원소 삽입 - 복잡도

원소의 개수가 n인 최대 힙에 새로운 원소 삽입
==> 부모 노드와의 대소 비교 최대 회수: log2n
최악 복잡도 O(logn)의 삽입연산

삽입 연산의 구현 - insert(item) 메서드

class MaxHeap:
    def insert(self, item):
        

** 힌트 : python에서 두 변수의 값 바꾸기
a = 3; b = 5
a, b = b, a ==> 변수의 값을 한번에 서로 바꿀 수 있다.

def insert(sef, item):
    self.data.append(item)
    # 배열로 보았을 때 가장 마지막에 삽입하기때문에 len(self.data)를 사용할 수 있다. 
    index = len(self.data)
    
    if index == 1
        return
    
    # 부모노드보다 삽입하려는 데이터의 크기가 클 동안 반복하도록 한다. 
    while self.data[index] > self.data[index//2] :
        self.data[index], self.data[index//2] = self.data[index//2], self.data[index]
        index = index//2
        
        # 루트노드이면 종료한다. 
        if index == 1:
            break