22강/23강: 힙(Heaps) (1) / (2)

강의

"힙"은 root node가 언제나 최대 또는 최소인 완전 이진 트리를 만족하는 자료구조 입니다.

 

모든 subtree는 최대 힙을 만족하지만 다른 subtree와의 관계는 정의되지 않습니다.

 

특정 키 값을 가지는 원소를 탐색하는 것에는 적절하지 않습니다.

 

노드의 추가/삭제는 마지막 노드에서만 가능합니다.

 

 

연산

• __init__() : 비어있는 힙 생성
• insert() : 원소 삽입
• remove() : 최대 원소 반환 및 제거

 

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

• node = m
• left child node = 2m
• right child node = 2m + 1
• parent node = m // 2

 

최대/최소 힙의 응용

• 우선순위 큐 (Priority Queue) : 시간 복잡도 O(log n)
• 힙 정렬 (heap sort) : 시간 복잡도 O(n log n)

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)
        
        m = len(self.data) - 1
        
        while m != 1:
            parentNum = m // 2
            
            if self.data[m] > self.data[parentNum]:
                self.data[m], self.data[parentNum] = self.data[parentNum], self.data[m]
                m = parentNum
                
            else:
                break

 

 

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 = i * 2
        right = i * 2 + 1

        smallest = i
        
        if left < len(self.data) and self.data[left] > self.data[smallest]:
        	smallest = left

        if right < len(self.data) and self.data[right] > self.data[smallest]:
			smallest = right

        if smallest != i:
        	self.data[i], self.data[smallest] = self.data[smallest], self.data[i]

            self.maxHeapify(smallest)