프로그래머스 강의_23

힙(Heaps)

최대 힙에서 원소의 삭제

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

최대 힙에서 원소의 삭제- 예

<최대 원소를 삭제해라!>
1. 루트 노드의 제거
2. 트리 마지막 자리 노드를 임시로 루트 노드의 자리에 배치
3. 자식 노드들과의 값 비교와 아래로, 아래로 이동
4. 자식 노드들 중 더 큰 키 값을 가지는 쪽으로 바꿔준다.

최대 힙으로부터 원소 삭제 - 복잡도

원소의 개수가 n인 최대 힙에서 최대 원소 삭제
=> 자식노드들과의 대소 비교 최대 회수: 2 X log2n
최악 복잡도 O(logn)의 삭제 연산

삭제 연산의 구현-remove() 메서드

class MaxHeap:
    def remove(self):
        if len(self.data) > 1:
            self.data[1],self.data[-1] = sellf.data[-1],self.data[1]
            data = self.data.pop(-1)
            self.maxHeapify(1)              
        #len(self.data)가 1일 경우 리스트가 비어있다는 뜻.
        else :
            data = None
        return data

삭제 연산의 구현 - maxHeapify() 메서드

class MaxHeap:
   def maxHeapify(self,i):
       left = 
       right = 
       smallest = i
       # 자신(i), 왼쪽 자식(left), 오른쪽 자식(right) 중 최대를 찾음
       # => 이것의 인덱스를 smallest에 담음
       if smallest !=i :
          # 현재 노드(i)와 최댓값 노드(smallest)의 값 바꾸기
          # 재귀적으로 maxHeapify를 호출

최대/최소 힙의 응용

1. 우선 순위 큐 (priority queue)

• Enqueue 할 때 "느슨한 정렬"을 이루고 있도록 합: O(logn)
• Dequeue 할 때 최댓값을 순서대로 추출: O(logn)
• 제 16강에서의 양방향 연결리스트 이용 구현과 효율성 비교

2. 힙 정렬 (heap sort)

• 정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입: O(logn)
• 삽입이 끝나면, 힙이 비게 될 때까지 하나씩 삭제: O(logn)
• 원소들이 삭제된 순서가 원소들의 정렬 순서
• 정렬 알고리즘의 복잡도 : O(nlogn)

3. 힙 정렬(heap sort)의 코드 구현

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

4. 연습문제

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):
    ## 왼쪽 자식의 인덱스와 오른쪽 자식의 인덱스를 계산한다.
    ## 자기자신은 i 
        left = i * 2
        right = i * 2 + 1
        smallest = i
    ## 왼쪽 자식이 존재 하는지 and 그 값이 원래 자기자신과 비교해 왼쪽 자식이 더 큰지 판단한다.
        if left < len(self.data) and self.data[smallest] < self.data[left]
            smallest = left
    ## 오른쪽 자식이 존재 하는지 and 그 값이 원래 자기자신과 비교해 오른쪽 자식이 더 큰지 판단하다.
        if right < len(self.data) and self.data[smallest] < self.data[right]
            smallest = right
    
        if smallest != i:
            self.data[i], self.data[smallest] = self.data[smallest],self.data[i]
            self.maxHeapiy(smallest)
    
    def solution(x):
        return 0