[자료구조] 힙(Heap) (Python)

1. 정의

-최댓값과 최솟값을 빠르게 찾기 위해 만들어진 완전 이진트리(complete Binary Tree)

#완전 이진트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

 

-종류에는 최대 힙과 최소 힙이 있음

 

2. 사용하는 이유

-최댓값과 최솟값을 빠르게 찾기 위해서

 

-최댓값 최솟값을 찾을 때 

배열을 사용하면 -> 시간 복잡도 O(n)

힙을 사용하면 -> 시간 복잡도 O(logn)

 

3. 구조

-완전 이진 트리 형태

 

-각 노드의 값이 해당 노드의 자식 노드의 값보다 크거나 같다(최대 힙) -> 최댓값이 rootnode에 담김

-각 노드의 값이 해당 노드의 자식 노드의 값보다 작거나 같다(최소 힙) -> 최솟값이 rootnode에 담김

 

4. Pyhon 모듈

#기본적으로 최소 힙 기능으로 작동한다.

 

import heapq: 모듈 import

heappush(): heap에 원소추가

heappop(): heap에서 원소 삭제

heapify(): list를 heap으로 만들기

 

물론 그냥 있는 모듈을 사용하는 게 가장 편한 방법이지만 원리에 조금 더 가까이 접근하기 위해 빙빙 돌아가는 구현을 해봅시다!

 

5. Python linked list로 maxheap구현

#maxheap코드 짜보기
class Heap:
    def __init__(self,data):
        self.heap_array = list()
        #안 헷갈리려고 index 1부터 시작
        self.heap_array.append(None)
        self.heap_array.append(data)
    
    #insert함수에서 바꿔줘야하는 작업 해야하는지 판별하는 함수
    def move_up(self,inserted_idx):
        #root node일 때
        if inserted_idx<=1:
            return False
        
        parent_idx = inserted_idx//2
        if self.heap_array[inserted_idx]>self.heap_array[parent_idx]:
            return True
        else:
            return False
    
    #delete함수에서 바꿔줘야하는 작업 해야하는지 판별하는 함수
    def move_down(self, pop_idx):
        left_child_pop_idx = pop_idx * 2
        right_child_pop_idx  = pop_idx * 2 + 1
        
        #1. 왼쪽 자식 노드도 없을 때
        if left_child_pop_idx>=len(self.heap_array):
            return False
        #2. 왼쪽 자식 노드는 있고 오른쪽 자식 노드는 없을 떄
        elif right_child_pop_idx>=len(self.heap_array):
            if self.heap_array[pop_idx]<self.heap_array[left_child_pop_idx]:
                return True
            else:
                return False
        #3. 왼쪽 자식, 오른쪽 자식 둘 다 있을 때
        else:
            if self.heap_array[left_child_pop_idx]>self.heap_array[right_child_pop_idx]: #자식 노드 중 왼쪽이 더 클 때
                if self.heap_array[popped_idx]<self.heap_array[left_child_pop_idx]:
                    return True
                else:
                    return False
                
            else:
                if self.heap_array[popped_idx]<self.heap_array[right_child_pop_idx]: #자식 노드 중 오른쪽이 더 클 때
                    return True
                else:
                    return False
                
                
    #새로운 노드 추가하는 함수    
    def insert(self,data):
        #Root node에 아무것도 없다면
        if len(self.heap_array) == 0:
            self.heap_array.append(None)
            self.heap_array.append(data)
            return True
        
        self.heap_array.append(data)
        #일단 넣어주고 그 이후에 순서 바꿔야할 부분 고려
        inserted_idx = len(self.heap_array)-1
        
        while self.move_up(inserted_idx):
            parent_idx = inserted_idx//2
            self.heap_array[inserted_idx],self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx]
            inserted_idx = parent_idx
            return True  
        
        
    #max heap에서 맨 위의 루트노드를 삭제하고 다시 구조를 짜는 코드
    def pop(self):
        if len(self.heap_array) <= 1:
            return None
        
        #max 추출 -> 맨앞이랑 맨 뒤랑 바꿔줌
        pop_data = self.heap_array[1] #추출된 max node가 pop_data
        #완전한 heap구조가 될 때까지 맨 앞과 맨 뒤를 swap
        self.heap_array[1] = self.heap_array[-1]
        del self.heap_array[-1]
        pop_idx = 1
        
        while self.move_down(pop_idx):
            left_child_pop_idx = popped_idx * 2
            right_child_pop_idx = popped_idx * 2 + 1
            
            #왼쪽 자식노드는 있고, 오른쪽 자식노드 없을 때
            if right_child_pop_idx >= len(self.heap_array):
                if self.heap_array[pop_idx] < self.heap_array[left_child_pop_idx]:
                    self.heap_array[pop_idx], self.heap_array[left_child_pop_idx] = self.heap_array[left_child_pop_idx], self.heap_array[pop_idx]
                    pop_idx = left_child_pop_idx
            #왼쪽, 오른쪽 모두 자식노드 있을 때
            else:
                    if self.heap_array[left_child_pop_idx] > self.heap_array[right_child_pop_idx]:
                        if self.heap_array[pop_idx] < self.heap_array[left_child_pop_idx]:
                            self.heap_array[pop_idx], self.heap_array[left_child_pop_idx] = self.heap_array[left_child_popped_idx], self.heap_array[popped_idx]
                            pop_idx = left_child_pop_idx
                    else:
                        if self.heap_array[pop_idx] < self.heap_array[right_child_pop_idx]:
                            self.heap_array[pop_idx], self.heap_array[right_child_pop_idx] = self.heap_array[right_child_popped_idx], self.heap_array[popped_idx]
                            pop_idx = right_child_pop_idx

            return pop_data

 

[Insert 함수]

• 새로운 값을 추가하는 함수
• 일단 완전 이진트리처럼 새로운 값을 최하단 왼쪽에 삽입
• move_up함수를 통해 parent_node와 swap 해야 되는지 여부를 판별한 후, 구조가 안정화될 때까지 수정해줌

[pop 함수]

• 맨 위에 있는 max값을 추출한 후, 다시 구조를 짜는 함수
• root node가 사라지면 마지막 노드가 그 자리를 일단 채운다.
• 이후부터는 move_down함수를 통해 child_node와 swap 해야 되는지 여부를 판별한 후, 구조가 안정화될 때까지 수정해줌