힙 (Heaps)

• 이진 트리의 한 종류 (이진 힙 - binary heap)

• 이진힙은 특별한 조건들을 만족하는 이진 트리

• 루트(root) 노드가 언제나 최대값 또는 최소값을 가진다

  • 최대값을 가지면 최대 힙(max heap), 최소값을 가지면 최소 힙(min heap)

• 완전 이진 트리여야 한다

• 최대 힙 내의 임의의 노드를 루트로 하는 서브트리 또한 최대 힙(재귀적으로 정의가 됨)
  

이진 탐색 트리와의 비교

• 원소들은 완전히 크기 순으로 정렬되어 있는가?

  → 이진탐색트리는 크기순으로 정렬이 가능하다 | 이진 힙은 그렇지 않다

• 특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가?

  → 이진탐색트리는 가능 | 이진 힙은 불가능

• 부가의 제약 조건은 어떤 것인가?

  → 이진 힙은 이진탐색트리에 비해 완전 이진트리여야한다

최대 힙(max heap)의 추상적 자료구조

연산의 정의

• init() : 비어 있는 최대 힙을 생성
• insert(item) : 새로운 원소를 삽입
• remove() : 최대 원소(root node)를 반환하고 삭제

데이터 표현의 설계

배열을 이용한 이진 트리의 표현

코드 구현

class MaxHeap:
    # 빈 힙을 생성
    def __init__(self):
        self.data = [None]

최대 힙에 원소 삽입

• 트리의 마지막 자리에 새로운 원소를 임시로 저장
• 부모 노드의 키 값을 비교하여 위로, 비교하고 위로 이동

코드 구현

class MaxHeap:
    def insert(self, item):
        # 흰트 - python에서 두 변수의 값 바꾸기
        # a = 3, b = 5
        # a, b  = b, a
        self.data.append(item)
        
        index = len(self.data) -1
    
        while index != 1:
            numOfParentNode = index//2
            print(numOfParentNode)
            
            if self.data[numOfParentNode] < self.data[index]:
                self.data[numOfParentNode], self.data[index] = self.data[index], self.data[numOfParentNode]
                index = numOfParentNode
            else:
                break

최대 힙에 원소 삽입의 복잡도

• 원소 개수가 n 인 최대 힙에 새로운 원소 삽입

  → 부모 노드와 대소 비교 최대 회수 : log(2)N

• 최악 복잡도 O(logN)의 삽입 연산

---

[실습] 최대 힙에 새로운 원소 삽입

문제

어서와! 자료구조와 알고리즘은 처음이지? 22강 실습: 최대 힙에 새로운 원소 삽입

문제 설명

초기 코드에 주어진 class MaxHeap 에 최대 힙에 새로운 원소를 추가하는 연산인 insert() 메서드의 구현을 완성하세요.

[참고 1] solution() 함수의 구현은 그대로 두세요. 이것을 없애면 테스트가 되지 않습니다.

[참고 2] 코드 실행 을 눌렀을 때 통과하는 것은 아무런 의미가 없습니다.

---

나의 풀이

solution.py

class MaxHeap:

    def __init__(self):
        self.data = [None]

    def insert(self, item):
        self.data.append(item)
        
        index = len(self.data) - 1
        
        while index != 1:
            numOfParentNode = index // 2
            print(numOfParentNode)
            
            if self.data[numOfParentNode] < self.data[index]:
                self.data[numOfParentNode], self.data[index] = self.data[index], self.data[numOfParentNode]
                index = numOfParentNode
            else:
                break

def solution(x):
    return 0