힙 (Heap) (3)

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

• 힙 클래스 구현 4 - delete 1

 

보통 삭제는 최상단 노드 (root node)를 삭제하는 것이 일반적이다. 왜냐하면 힙의 용도는 최대값 또는 최소값을 root node에 놓아서, 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것이기 때문이다.

 

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(data)

    def pop(self):
        if len(self.heap_array) <= 1:	# 길이가 1 이하라는 것은 데이터가 None 혹은 None 조차도 없는 상황을 의미한다.
            return None		# False 보다는 노드에 있는 값을 리턴하기 때문에 None을 리턴하면 충분하다.
        
        returned_data = self.heap_array[1]	# 인덱스 1번의 데이터가 이 경우에 최대값이기 때문. 별도로 삭제하는 코드는 넣지 않아도 된다. 어차피 이따가 밑에 데이터로 덮어씌울 것이기 때문
        return returned_data

 

• 힙 클래스 구현 4 - delete 2

상단의 데이터 삭제 시, 가장 최하단부 왼쪽에 위치한 노드 (일반적으로 가장 마지막에 추가한 노드)를 root node로 이동시킨다. 그리고 root node의 값이 child node보다 작을 경우, root node의 child node 중 가장 큰 값을 가진 노드와 root node의 위치를 바꿔주는 작업을 반복한다. (swap)

 

앞서도 알아봤지만, 특정 노드의 관련 위치 알아내는 방법은 다음과 같다.

• 부모 노드 인덱스 번호 (parent node's index) = 자식 노드 인덱스 번호 (child node's index) // 2
• 왼쪽 자식 노드 인덱스 번호 (left child node's index) = 부모 노드 인덱스 번호 (parent node's index) * 2
• 오른쪽 자식 노드 인덱스 번호 (right child node's index) = 부모 노드 인덱스 번호 (parent node's index) * 2 + 1

 

https://www.fun-coding.org/00_Images/heap_remove.png

 

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

        # case 1: 왼쪽 자식 노드도 없을 때
        if left_child_popped_idx >= len(self.heap_array):	# array의 길이는 항상 전체 length에서 1을 더하게 되어 있다. len(array) - 1 한 데까지 데이터가 쭉 있다.
            return False
        # case 2: 오른쪽 자식 노드만 없을 때
        elif right_child_popped_idx >= len(self.heap_array):
            if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                return True	# 위 조건에 부합하는 경우 swap을 해야 하므로, True를 리턴하는 것
            else:
                return False
        # case 3: 왼쪽, 오른쪽 자식 노드 모두 있을 때
        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	# 추출된 데이터는 root에 위치해 있기 때문에 항상 1부터 시작한다

        while self.move_down(popped_idx):	# 조건에 부합할 경우 swap을 계속 해주는 반복문
            left_child_popped_idx = popped_idx * 2
            right_child_popped_idx = popped_idx * 2 + 1
            
            # case 2: 오른쪽 자식 노드만 없을 때
            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
            # case 3: 왼쪽, 오른쪽 자식 노드 모두 있을 때
            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

 

데이터 삭제 코드는 이렇게 된다.

 

이제 앞서 알아본 데이터 삽입 코드와 병합하면,

 

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None)
        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):
        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

    def move_down(self, popped_idx):
        left_child_popped_idx = popped_idx * 2
        right_child_popped_idx = popped_idx * 2 + 1

        # case 1: 왼쪽 자식 노드도 없을 때
        if left_child_popped_idx >= len(self.heap_array):
            return False
        # case 2: 오른쪽 자식 노드만 없을 때
        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
        # case 3: 왼쪽, 오른쪽 자식 노드 모두 있을 때
        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
            
            # case 2: 오른쪽 자식 노드만 없을 때
            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
            # case 3: 왼쪽, 오른쪽 자식 노드 모두 있을 때
            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)
print(heap.heap_array)

print(heap.pop())
print(heap.heap_array)

 

 

이렇게 pop()이 정상 작동하는 것을 알 수 있다.

 

5. 힙 (Heap) 시간 복잡도

• depth (트리의 높이)를 h라고 표기한다면,
• n개의 노드를 가지는 heap에 데이터 삽입 또는 삭제시, 최악의 경우 root node에서 leaf node까지 비교해야 하므로 h = log n 에 가까우므로 시간 복잡도는 O(log n).
  • 참고: 빅오 표기법에서 log n 에서의 밑은 10이 아니라 2이다.
  • 한 번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미이다. 즉, 50%의 실행시간을 단축시킬 수 있다는 것을 의미한다.

 

 

 

 

 

[참고자료]

패스트캠퍼스 개발자 취업 합격 패스 With 코딩테스트, 기술면접 초격차 패키지 Online 강의자료