힙

📌힙 (Heaps)

이진 트리의 한 종류로 이진 힙 (binary heap) 이라고도 부른다.

1. 루트(root)노드가 언제나 최댓값 또는 최솟값을 가짐
   최대 힙 max heap : 원소의 순서 기준이 내림차순이다.
   최소 힙 min heap : 원소의 순서 기준이 오름차순이다.
2. 완전 이진 트리여야함

힙 정렬 (heap sort) : 힙을 이용하여 데이터를 정렬하는 알고리즘

이진 탐색 트리와의 비교

1. 원소들은 완전히 크기 순으로 정렬되어 있는가?
   최대,최소 힙 : X 느슨한 정렬이다
   이진 탐색 트리 : O
2. 특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가?
   최대,최소 힙 : X
   이진 탐색 트리 : O
3. 부가의 제약 조건은 어떤 것인가?
   최대,최소 힙 : 완전 이진트리여야 한다.
   이진 탐색 트리 : 상관 없음

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

• 연산의 정의
  __init__() - 빈 최대 힙을 생성
  insert(item) - 새로운 원소를 삽입
  remove() - 최대 원소(root node)를 반환(그리고 동시에 이 노드를 삭제)
  

데이터 표현의 설계

배열을 이용한 이진 트리의 표현 - 완전 이진 트리이기 때문에 배열 구현이 적절

최대 힙에 원소 삽입

1. 트리의 마지막 자리에 새로운 원소를 임시로 저장

2. 부모 노드와 키 값을 비교하여 위로 이동(부모노드와 자리를 바꿈) 부모노드가 자식 노드보다 값이 크다는 전제 조건을 만족할 때까지 이동
   💡파이썬에서 두 변수의 값 바꾸기
   a=3; b=5
   a,b = b,a

    class MaxHeap:
   
       def __init__(self): 
           self.data = [None] # 0번 인덱스 버리니까 
   
       def insert(self, item):
           self.data.append(item)
           index = len(self.data) - 1
   
           while index > 1:
               if self.data[index // 2] < self.data[index]:
                   self.data[index // 2], self.data[index] = self.data[index], self.data[index // 2]
                   index //= 2
               else:
                   break
   
   def solution(x):
       return 0

   
   

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

원소의 개수가 n인 최대 힙에 새로운 원소 삽입
-> 부모 노드와의 대소 비교 최대 회수 : log2n

최악 복잡도O(logn)의 삽입 연산👍

최대 힙에 원소 삭제

1. 루트 노드의 제거 - 이것이 원소들 중 최댓값
2. 트리 마지막 자리 노드를 임시로 루트 노드의 자리에 배치
3. 자식 노드들과의 값 비교와 아래로 이동.
   자식은 둘 있을 수도 있는데 어느 쪽으로 이동? 둘 중 더 큰 쪽

class MaxHeap:

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


    def remove(self):
        if len(self.data) > 1:
            self.data[1], self.data[-1] = self.data[-1], self.data[1]
            data = self.data.pop(-1)
            self.maxHeapify(1)
        else:
            data = None
        return data


    def maxHeapify(self, i):
        # 왼쪽 자식 (left child) 의 인덱스를 계산
        left = 2*i
        # 오른쪽 자식 (right child) 의 인덱스를 계산
        right = 2*i+1
        smallest = i
        # 왼쪽 자식이 존재하는지, 그리고 왼쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단
        if 1 < left < len(self.data) and self.data[left] > self.data[smallest]:
        # 조건이 만족하는 경우, smallest 는 왼쪽 자식의 인덱스를 가짐    
		smallest = left

        # 오른쪽 자식이 존재하는지, 그리고 오른쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단
        if 1 < right < len(self.data) and self.data[right] > self.data[smallest]:
		smallest = right

        if smallest != i:
        # 현재 노드 (인덱스 i) 와 최댓값 노드 (왼쪽 아니면 오른쪽 자식) 를 교체 
		self.data[i], self.data[smallest] = self.data[smallest], self.data[i]

        # 재귀적 호출을 이용하여 최대 힙의 성질을 만족할 때까지 트리를 정리
           	self.maxHeapify(smallest)


def solution(x):
    return 0

최대 힙에 원소 삭제의 복잡도

원소의 개수가 n인 최대 힙에 새로운 원소 삭제
-> 자식 노드들과의 대소 비교 최대 회수 : 2 X log2n

최악 복잡도O(logn)의 삭제 연산👍

✍최대/최소 힙의 응용

1. 우선 순위 큐 (priority queue)
   - Enqueue할 때 "느슨한 정렬"을 이루고 있도록 함: O(logn)
   - Dequeue 할 때 최댓값을 순서대로 추출: O(logn)
   -> 양방향 연결 리스트로 구현한 것보다 시간적으로 효율적이다.
   
   

2. 힙 정렬 (heap sort)
   - 정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입: O(logn)
   - 삽입이 끝나면, 힙이 비게 될 때까지 하나씩 삭제: O(logn)
   - 원소들이 삭제된 순서가 원소들의 정렬 순서(min heap이면 오름차순, max heap이면 내림차순)
   - 정렬 알고리즘의 복잡도: O(nlogn)

   
   

   힙 정렬의 코드 구현

   def heapsort(unsorted):
     H = MaxHeap()
         H.insert(item)
     sorted = []
     d = H.remove()
     while d:
       sorted.append(d)
       d = H.remove()
   
     return sorted