[자료구조] 힙(Heap) - 2. 파이썬 구현

* 해당 글은 패스트캠퍼스의 자료구조 알고리즘 강의를 듣고 정리하였습니다. 저작권은 패스트캠퍼스에 있습니다.

📌힙과 배열

일반적으로 힙 구현시 배열 자료구조를 활용한다.

주의할 점은 배열은 인덱스가 0부터지만, 힙 구현의 편의를 위해 root의 인덱스를 1로 지정한다.

배열로 힙을 구현

• 부모 인덱스 번호 = 자식 노드 인덱스 번호 // 2
• 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2
• 오른쪽 자식 노드 인덱스 번호 = 부모  노드 인덱스 번호 *2 + 1

 

 

📌 힙에서 데이터 삽입 구현 (Max Heap)

✔️  move_up, insert 구현

class Heap:
    def __init__(self, data):
    	# 배열로 힙을 구현
        self.heap_array = list()
        # heap_array[0]은 사용하지 않음
        self.heap_array.append(None)
        # heap_array[1]은 root
        self.heap_array.append(data)
        
    def move_up(self, inserted_idx): # 부모 노드와 자식노드 크기를 비교함
        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
        
    def insert(self, data):
    	# heap에 아무것도 들어있지 않은 경우. 예외처리
        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           

✔️ 구현 확인 하기

heap = Heap(15)
heap.insert(10)
heap.insert(8)
heap.insert(5)
heap.insert(4)
heap.insert(20)
print(heap.heap_array)
# 결과 : [None, 20, 10, 15, 5, 4, 8]

 

 

📌힙에 데이터 삭제 구현 (Max Heap)

힙에서 데이터 삭제는 root에서만 일어난다고 가정한다.

1. root 삭제후, 가장 마지막에 추가한 노드를 root로 이동한다.
2. root 노드 값이 자식 노드보다 작다면, swap을 반복한다.

데이터 삭제는 간단히 위와 같지만, case는 총 3가지로 나눌 수 있다.

1. 왼쪽 자식 노드도 없고, 오른쪽 자식 노드도 없는 경우
   
   • 이 경우 왼쪽 자식이 있는지만 확인하면 오른쪽도 없음
   • 더 이상 swap할 것이 없음. 중단
2. 왼쪽 자식 노드는 있는데, 오른쪽 자식 노드가 없는 경우
   • 왼쪽 자식 노드와 현재 노드를 비교하여, 왼쪽 자식이 더 크다면 swap
3. 왼쪽 오른쪽 자식 노드 모두 있는 경우
   • 왼쪽 자식 노드와 오른쪽 자식 노드 크기를 비교해 큰 값을 고름
   • 자식 노드와 현재 노드를 비교해, 자식이 더 크다면 swap

삭제 case 

위의 case를 사용해 move_down 함수를 구현하여, swap해야 할 지 말지를 반환한다.

pop 함수는 move_down의 결과에 따라 삭제 동작을 수행한다.

 

 

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(data)
    
    def move_down(self, popped_idx):
        left_child_popped_idx = popped_idx * 2
        right_child_popped_idx = popped_idx * 2 + 1
        
        # case1: 왼쪽 자식 노드도 없을 때
        if left_child_popped_idx >= len(self.heap_array):
            return False
        # case2: 오른쪽 자식 노드만 없을 때
        elif right_child_popped_idx >= len(self.heap_array):
            if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                return True
            else:
                return False
        # case3: 왼쪽, 오른쪽 자식 노드 모두 있을 때
        else:
            if self.heap_array[left_child_popped_idx] > self.heap_array[right_child_popped_idx]:
                if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                    return True
                else:
                    return False
            else:
                if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]:
                    return True
                else:
                    return False
    
    def pop(self):
        if len(self.heap_array) <= 1:
            return None
        
        returned_data = self.heap_array[1]
        self.heap_array[1] = self.heap_array[-1]
        del self.heap_array[-1]
        popped_idx = 1
        
        while self.move_down(popped_idx):
            left_child_popped_idx = popped_idx * 2
            right_child_popped_idx = popped_idx * 2 + 1

            # case2: 오른쪽 자식 노드만 없을 때
            if right_child_popped_idx >= len(self.heap_array):
                if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                    self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[left_child_popped_idx], self.heap_array[popped_idx]
                    popped_idx = left_child_popped_idx
            # case3: 왼쪽, 오른쪽 자식 노드 모두 있을 때
            else:
                if self.heap_array[left_child_popped_idx] > self.heap_array[right_child_popped_idx]:
                    if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                        self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[left_child_popped_idx], self.heap_array[popped_idx]
                        popped_idx = left_child_popped_idx
                else:
                    if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]:
                        self.heap_array[popped_idx], self.heap_array[right_child_popped_idx] = self.heap_array[right_child_popped_idx], self.heap_array[popped_idx]
                        popped_idx = right_child_popped_idx
        
        return returned_data
    
    def move_up(self, inserted_idx):
        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

    def insert(self, data):
        if len(self.heap_array) == 1:
            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    

 

✔️ 구현 결과 확인

heap = Heap(15)
heap.insert(10)
heap.insert(8)
heap.insert(5)
heap.insert(4)
heap.insert(20)
print(heap.heap_array)
# 결과 [None, 20, 10, 15, 5, 4, 8]
heap.pop()
heap.pop()
print(heap.heap_array)
# 결과 [None, 10, 5, 8, 4]

 

📌 최대힙을 이용한 최소힙 구현 (꼼수)

최소 힙의 경우엔 최대 힙 코드를 수정하여 구현할 수 도 있겠지만, 

힙에 넣는 값의 부호를 반전(-)하여 구현할 수 있다. 일종의 꼼수!

아래와 같은 최소 힙의 경우를, 다음과 같이 부호를 반전하여 삽입하면 최소힙과 유사한 결과를 얻을 수 있다.

물론 결과 값에 (-)처리를 해줘야한다!

최소힙

heap = Heap(-15)
heap.insert(-10)
heap.insert(-8)
heap.insert(-5)
heap.insert(-4)
heap.insert(-20)
print(heap.heap_array)
# [None, -4, -5, -10, -15, -8, -20]
heap.pop()
heap.pop()
print(heap.heap_array)
# [None, -8, -15, -10, -20]

 

 

 

 

📌 힙의 시간 복잡도

✔️ 데이터를 삽입/삭제 : O(logn)

✔️ 최대/ 최소값 찾기 : O(1)