힙 (Heap)

힙에서 원소의 삭제

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

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

원소의 개수가 n인 최대 힙에서 최대 원소 삭제

• 자식 노드들과의 대소 비교 최대 횟수: 2*log_2n
• 최악 복잡도 o(logn)의 삭제 연산

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

class MaxHeap:
	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) # 1번부터 max 만족하게 내려간다는 뜻
        else:
        	data = None
        return data

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)
• 양방향 연결 리스트 이용 구현과 효율성 비교

2. 힙 정렬 (heap sort)

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

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

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