[자료구조] 힙(Heap) 구현(삽입, 삭제)

힙 구현

• 일반적으로 힙 구현시 배열을 활용
• 힙 구현의 편의를 위해, 루트 노드 인덱스를 1로 지정함
  • 부모 노드 인덱스 = (자식 노드 인덱스) // 2
  • 왼쪽 자식 노드 인덱스 = (부모 노드 인덱스) * 2
  • 오른쪽 자식 노드 인덱스 = (부모 노드 인덱스) * 2 + 1

 

 

 

힙 데이터 삽입 구현

# 힙 클래스 구현
class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(data) # 인덱스 1번부터 데이터가 삽입

    # 삽입된 노드와 부모 노드 비교해서, 삽입된 노드가 위로 이동해야 하는지 결정
    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) == 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] # swap
            inserted_idx = parent_idx
        
        return True


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

 

 

 

힙 데이터 삭제 구현 (Max 힙)

• 보통 삭제는 루트 노드를 삭제하는 것이 일반적
  • 힙의 용도는 최댓값 또는 최솟값을 루트 노드에 두어서, 바로 꺼내 쓸 수 있도록 하는 것!

# 힙 클래스 구현
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: # 힙에 데이터가 None만 있거나 아예 없을 경우
            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): # 이동해야만 하는 Case에서 True가 나올 경우
            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


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

heap.pop() # 20

heap.heap_array # [None, 15, 10, 8, 5, 4]

 

 

 

힙 시간복잡도

n개의 노드를 가지는 힙에 데이터를 삽입 또는 삭제 시,
최악의 경우, 루트 노드에서 리프 노드까지 비교해야 하므로, (depth(트리의 높이)가 약 log(n))
▶ 시간복잡도는 O(log(n))