파이썬 자료구조 (7) 힙

1. 힙(Heap)

• 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리
• 완전 이진 트리(Complete Binary Tree): 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

 

2. 힙의 구조

• 힙은 최댓값을 구하기 위한 구조(최대 힙, Max Heap)와 최솟값을 구하기 위한 구조(최소 힙, Min Heap)로 분류할 수 있음
• 최대 힙의 경우 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다
• 완전 이진 트리 형태

 

3. 힙과 이진 탐색 트리의 공통점 및 차이점

• 공통점: 둘 다 이진 트리
• 차이점
  • 힙은 각 노드의 값이 자식 노드보다 크거나 같다(Max Heap) 또는 작거나 같다(Min Heap)
  • 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 순으로 값이 커짐
  • 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건을 따르지 않음

 

4. 힙의 동작(예시: Max Heap)

(1) 먼저 삽입된 데이터는 완전 이진 트리 구조에 맞춰 최하단부 왼쪽 노드부터 채워짐

 

(2) 채워진 노드 위치에서 부모 노드보다 값이 클 경우 부모 노드와 위치를 바꿔주는 작업을 반복함(swap)

 

(3) 힙의 데이터 삭제 방법

• 힙은 보통 최댓값 또는 최솟값을 root 노드에 놓아서 바로 꺼내 쓰도록 하기 때문에 최상단 노드(root 노드)를 삭제하는 것이 일반적
• 상단의 데이터 삭제 시 가장 최하단부 쪽 일반적으로 가장 마지막에 추가한 노드를 root 노드로 이동
• root 노드의 값이 child node보다 작을 경우 root 노드의 child node 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔 주는 작업을 반복(swap)

 

 

 

5. 힙 구현하기

• 일반적으로 힙 구현 시 배열 자료구조를 활용
• 배열은 인덱스가 0번부터 시작하지만 힙 구현의 편의를 위해 root 노드 인덱스 번호를 1로 지정하면 아래와 같은 성질이 성립하기 때문에 구현이 수월해짐
  • 부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 // 2
  • 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2
  • 오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2 + 1

 

class Heap:
    def __init__(self, data):
      self.heap_array = list()
      self.heap_array.append(None)    # 0번 인덱스를 사용하지 않기 위해
      self.heap_array.append(data)

heap = Heap(15)
heap.heap_array

 

 

5-1. insert 구현하기

class Heap:
    def __init__(self, data):
      self.heap_array = list()
      self.heap_array.append(None)		# 0번 인덱스를 사용하지 않기 위해
      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

heap = Heap(15)
heap.insert(10)
heap.insert(8)
heap.insert(5)
heap.insert(4)

heap.heap_array

heap.insert(20)
heap.heap_array

 

 

5-2. 삭제 구현하기

# 보통 삭제는 최상단 노드(root 노드)를 삭제하는 것이 일반적임
# 힙의 용도는 최댓값 또는 최솟값을 root 노드에 놓아서 최댓값과 최솟값을 바로 꺼내 쓸 수 있도록 하는 것

    def pop(self):
        if len(self.heap_array) <= 1:
            return None

        returned_data = self.heap_array[1]
        return returned_data
        
# 상단의 데이터 삭제 시 가장 최하단부 왼쪽(현재 그림에서만 해당 일반적으로 가장 마지막에 추가한 노드)에 위치한 노드(일반적으로 가장 마지막에 추가한 노드)를 root 노드로 이동
# root 노드의 값이 child node보다 작을 경우 root 노드의 child node 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업을 반복함(swap)

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

        # 양쪽 다리가 없는 경우
        if left_child_popped_idx >= len(self.heap_array):
            return False
        # 왼쪽 다리만 있을 경우
        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
        # 양쪽 다리가 있을 경우
        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

            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
            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

heap.pop()

heap.heap_array

 

 

전체 코드

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

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

        if left_child_popped_idx >= len(self.heap_array):
            return False
        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
        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

            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
            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