힙 (Heap) (2)

4. 힙 구현

힙과 배열

일반적으로 힙 구현 시 배열 자료구조를 활용한다. 배열은 인덱스가 0번부터 시작하지만, 힙 구현의 편의를 위해, root node 인덱스 번호를 1로 지정하면, 구현이 조금 더 수월하다.

• 부모 노드 인덱스 번호 (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_array.png

 

위 그림을 보면, 가령 10 노드의 인덱스 번호가 2인데, 10 노드의 부모 노드 인덱스는 2 // 2 (2에서 2를 나눈 몫)으로 1이다. 또, 15 노드의 왼쪽 자식 노드인 10 노드의 인덱스 번호는 1 * 2인 2이다. 10 노드의 오른쪽 자식 노드인 4 노드의 인덱스 번호는 2 * 2 + 1인 5이다.

 

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

• 힙 클래스 구현 1

# 힙 클래스 구현 1
class Heap:
    def __init__(self, data):
        self.heap_array = list()	# heap_array라는 리스트 생성
        self.heap_array.append(None)	# 힙의 복잡도를 떨어트리기 위해 맨 처음 데이터는 None으로 설정
        self.heap_array.append(data)

 

위 코드를 보면, 힙 구현의 편의를 위해 root node의 인덱스 번호를 1로 설정하였다. 배열의 첫 번째 인덱스는 0인데, 일부러 첫 번째 인덱스에 들어가는 값을 None으로 설정하고, 1부터 시작하도록 한 것이다.

 

이 코드를 테스트 해보면,

 

heap = Heap(1)
print(heap.heap_array)

 

 

이렇게 인덱스 0의 값은 None으로, 인덱스 1의 값에는 1이 잘 들어가 있는 것을 알 수 있다.

 

• 힙 클래스 구현 2 - insert 1

insert 메서드에서도 마찬가지로 인덱스 번호가 1번부터 시작하도록 변경한다.

 

# 힙 클래스 구현 1
class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(data)

    # 힙 클래스 구현 2 - insert 1
    def insert(self, data):
        if len(self.heap_array) == 0:	# 혹시나 해서 heap_array에 데이터가 없는 경우에, root node의 인덱스를 1로 설정해주는 작업
            self.heap_array.append(None)
            self.heap_array.append(data)
            return True

        self.heap_array.append(data)	# heap_array에 데이터가 이미 있다면, 그냥 append
        return True

 

이렇게 기본적인 insert 처음 부분을 만들면, 이제는 root node에 가장 큰 노드가 들어가고, 부모 노드(parent node)가 자식 노드(child node)보다 값이 큰 상태가 되도록 위치를 바꾸는 작업을 수행해야 한다.

 

• 힙 클래스 구현 3 - insert 2
  • 삽입한 노드가 부모 노드의 값보다 클 경우, 부모 노드와 삽입한 노드 위치를 바꿈
  • 삽입한 노드가 루트 노드가 되거나, 부모 노드보다 값이 작거나 같을 경우까지 반복

 

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

 

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):	# inserted_idx라는 데이터를 받아서 이 노드와 상위 노드와의 관계를 판단하는 메서드
        if inserted_idx <= 1:
            return False	# 아래에 insert 메서드에서 반복문을 종료시키는 것

        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):	# True인 상황에서는 계속 반복
            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

 

최대 힙(Max Heap)에서의 삽입 코드는 위와 같다.

 

이것을 테스트 해보면,

 

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

 

 

이렇게 None 다음에 첫 번째 index의 값으로 20이 최대값으로 잘 출력되는 것을 알 수 있다.

 

 

 

 

 

[참고자료]

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