[프로그래머스 알고리즘] 22강, 23강: 힙(Heaps)

힙 (Heaps)

이진 트리의 한 종류로 다음 조건을 만족시킴 :

1. 루트 노드가 언제나 최댓값 또는 최솟값을 가짐 - max heap / min heap
2. 완전 이진 트리여야 함

재귀적 정의 : 어느 노드를 루트로 하는 서브 트리도 모두 최대 힙이면 된다.

 

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

 

최대 힙의 추상적 자료 구조

• __init__() : 빈 최대 힙을 생성
• insert(item) : 새로운 원소를 삽입
• remove() : 최대 원소(root)를 반환

 

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

 

 

최대 힙에 원소 삽입

원소의 개수가 n인 최대 힙에 새로운 원소를 삽입하는 것이므로 최악 복잡도는 O(logn)이 된다.

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

최대 힙에서 원소의 삭제

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

 

원소 삭제의 복잡도

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

자식 노드들과의 대소비교 최대 회수가 2logn이므로 최악복잡도 O(logn)이다.

 

최소 / 최대 힙의 응용

1. 우선 순위 큐
   • enqueue할 때 느슨한 정렬을 이루고 있도록 함 : O(log n)
   • dequeue할 때 최댓값을 순서대로 추출 : O(log n)
   • 16강의 양방향 연결 리스트 이용 구현과 효율성 비교
2. 힙 정렬 (Heap Sort)
   • 정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입 : O(log n)
   • 삽입이 끝나면, 힙이 비게 될 때까지 하나씩 삭제 : O(log n)
   • 원소들이 삭제된 순서가 원소들의 정렬 순서
   • 정렬 알고리즘의 복잡도 : O(nlogn)

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

 

---

22강 실습: 최대 힙에 새로운 원소 삽입

class MaxHeap:

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


    def insert(self, item):
        self.data.append(item)
        insert_idx = self.data.index(item)
        parent_idx = insert_idx  // 2
        while (parent_idx >= 1) and (self.data[parent_idx] < item) :
            self.data[parent_idx], self.data[insert_idx] = item, self.data[parent_idx]
            insert_idx = parent_idx
            parent_idx = insert_idx // 2

 

23강 실습: 최대 힙에서의 원소 삭제

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 (left < len(self.data)) and (self.data[left] > self.data[smallest]):
            # 조건이 만족하는 경우, smallest 는 왼쪽 자식의 인덱스를 가집니다.
            smallest = left

        # 오른쪽 자식이 존재하는지, 그리고 오른쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if (right < len(self.data)) and (self.data[smallest] < self.data[right]):
            # 조건이 만족하는 경우, smallest 는 오른쪽 자식의 인덱스를 가집니다.
            smallest = right

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

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