[자료구조와 알고리즘] #8. 힙(Heap)

이 힙 아님 주의

---

#8. 힙(Heap)

힙이란

• 이진트리의 한 종류 (binary heap)
• 루트 노드가 언제나 최대값 혹은 최소값을 가짐 (최대힙 : max heap, 최소힙 : min heap) 
  • 루트, 부모가 다른 노드들보다 항상 최대/최소 
  • 재귀적으로도 어느 노드를 루트로 하는 서브트리도 모두 최대/최소힙 
  • 다만 느슨한 정렬 : 왼쪽에 있는 노드가 무조건 숫자가 작거나 무조건 크진 않음 
• 완전 이진 트리여야 함 

연산의 정의 (in case of 최대힙)

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

 

데이터 표현의 설계 

배열을 이용한 이진 트리의 표현 (1부터 시작) 

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

최대 힙에 원소 삽입

• 트리의 마지막 자리에 새로운 원소를 임시로 저장
• 부모 노드와 키 값을 비교하여 쭉 위로~ 이동 
• 복잡도 
  • 원소의 개수 n인 최대힙에 새로운 원소 삽입 시 부모 노드와의 대소 비교 최대 회수 : log2n  
  • 최악복잡도는 O(logn) 

class MaxHeap:

    #a,b = b,a 활용
    
	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 = index //2                        #인덱스를 부모 인덱스로 변경 
            else : break

최대 힙에 원소 삭제

최대힙 → 최대값을 순서대로 뽑아내는 것이 주 관심 → 루트노드에서 원소 삭제 진행 

• 루트 노드 제거 (최대값) 
• 트리 마지막 자리 노드(마지막 인덱스)를 임시로 루트 노드의 자리에 배치 (완전이진트리 모양 유지)
• 자식노드들과의 값을 비교해서 아래로 쭉 이동 
  • 자식이 둘 있을 경우 → 둘 중에 더 큰 값 쪽으로 이동 
• 복잡도 : 자식 노드들과의 대소 비교 최대 회수 2 * log2n , 최악 복잡도 : O(logn) 

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) #끝으로 바뀐 루트 데이터를 pop  
            
            #완전이진트리로 구조 변경 
            self.maxHeapify(1) #1 : 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[right] > self.data[smallest]:
            # 조건이 만족하는 경우, smallest 는 오른쪽 자식의 인덱스를 가집니다.
            smallest = right

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

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

 

최대/최소힙 응용

우선순위 큐

• Enqueue 할 때 느슨한 정렬을 이루고 있도록 함 (O(logn)) 
• Dequeue할 때 최대값을 순서대로 추출 (O(logn))
• 양방향 연결리스트 이용하는 것 보다 시간적 효율성이 높음  

힙 정렬 

• 정렬되지 않은 원소들을 아무 순서대로 최대 힙에 삽입 (O(logn))
• 삽입이 끝나면 힙이 빌 때 까지 하나씩 삭제 (O(logn))
• 원소들이 삭제된 순서가 원소들의 정렬 순서 (O(nlogn))

def heapsort(unsorted):   #list

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

 

 

---

앞으로 더 배워두면 좋을 내용들 

• 그래프의 기초와 그래프 탐색
  탐색의 효율을 높이는 트리들: red-black tree, AVL tree 등
  정렬 알고리즘 심화
  탐색 알고리즘 심화
  B-tree, B+-tree 등
• 스트링/패턴 매칭
  데이터 압축
  정보 암호화