파이썬으로 Heap 구현하기

힙(heap)은 이진 힙(binary heap)이라고도 하며, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기본으로 한 자료구조이다.

 

힙은 다음과 같은 속성을 가지고 있다.

1. 완전 이진트리(Complete Binary Tree) 이다.
2. 부모노드의 키값과 자식노드의 키값 사이에는 대소관계가 성립한다.
   • 키값 대소관계는 오로지 부모자식 간에만 성립되며 형제사이에는 대소관계가 정해지지 않음

 

Heap 재구조화(Heapify)

힙에서 원소의 삽입이나 삭제가 일어나면 최대 힙의 조건이 깨질 수 있다. 이 경우 다시 최대 힙의 조건을 만족하도록 노드의 위치를 바꾸는 것을 재구조화(heapify)라고 한다. 

삽입과 삭제의 경우 연산 자체는 O(1)의 시간 복잡도로 작동하지만, heapify의 과정이 O(logN)이기 때문에 최종적으로 O(logN)의 시간 복잡도를 가지게 된다. 

 

 

힙은 완전 이진트리이기에 배열로 간단하게 표현할 수 있으며 편의성과 가독성 때문에 인덱스 1부터 사용한다.(필수는 아님)

 

배열로 표현한 힙은 루트 노드의 인덱스가 1인 경우 다음과 같은 속성을 가진다.

• 노드 i의 부모노드 인덱스 : i // 2  
• 노드 i의 왼쪽 자식 노드 인덱스 : 2*i
• 노드 i의 오른쪽 자식 노드 인덱스 : 2*i + 1

 

나는 파이썬으로 Heap을 구현하면서 인덱스 0번 자리를 쓰는게 더 편했기에 루트 노드를 index 0에 두고 구현했다.

이 경우에는 이렇게 해주면 된다.

• 노드 i의 부모노드 인덱스 : (i - 1) // 2  
• 노드 i의 왼쪽 자식 노드 인덱스 : 2*i + 1
• 노드 i의 오른쪽 자식 노드 인덱스 : 2*i + 2

 

다음은 파이썬으로 구현해본 Max_Heap이다.

 

 

먼저 Heap 을 배열로 구현하기 위해 배열을 선언해준다.

class Heap:
    def __init__(self):
        self.heap = []

 

 

다음으로 Heap에 노드를 넣어주고 자식 노드가 부모 노드보다 크다면 정렬 시켜주는 메소드를 만들었다.

    def insert(self, data):
        self.heap.append(data)
        self.shift_up(len(self.heap) - 1)

  # 부모가 자식보다 작다면 부모와 자식의 위치를 바꿔준다.
    def shift_up(self, index):
        parent = (index - 1) // 2
        while index > 0 and self.heap[index] >= self.heap[parent]:
            self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
            index = parent
            parent = (index - 1) // 2

 

 

 

그리고 루트노드를 pop 하는 기능을 구현하려 했는데 이게 상당히 힘들었다.

index 0 을 빼오면 그 뒤에 있는 값들을 전부 다시 정렬시켜야 하는데 그냥 배열의 마지막 값을 pop 하는 것과는 너무 달라서 고생했다.

하나하나 풀어서 설명해보겠다.

 

    def left_pop(self):
        if not self.heap:
            return -1
            
        max = self.heap[0]
        current = self.heap[-1]
        self.heap[0] = current
        del(self.heap[-1])

        self.child_check = 0 
        index = 0
      
        return max

 

만약 heap이 비어 있다며 -1을 리턴해준다.

 

heap이 비어있지않다면

heap[0]이 루트 노드이므로 max에 값을 저장해주고 return max를 해줄 것 이다.

 

그리고 배열을 재정렬 시키기 위해

heap[0]에 heap[-1]을 넣어준다.

 

다음으로 child_check로 

heap[0]에 넣어준 값에 자식이 없다면 0

하나라면 1, 둘이라면 2를 넣어 확인할 것 이다.

    def shift_down(self, index):
        left_child = (index * 2) + 1
        right_child = (index * 2) + 2
            
        if left_child >= len(self.heap):
            return False

        elif right_child >= len(self.heap):
            if self.heap[left_child] > self.heap[index]:
                self.child_check = 1
                return True
            else:
                return False

 

부모의 값과 자식의 값을 비교하기 위한 메소드이다.

만약 왼쪽 자식의 인덱스가 배열의 길이 이상이라면

자식이 둘 다 없는 것 이므로 False

 

왼쪽 자식의 인덱스가 배열의 길이보다 작고 오른쪽 자식의 인덱스가 배열의 길이 이상이라면

왼쪽 자식만 존재하는 것이므로

child_check에 1을 넣어준다. 

이때 왼쪽 자식보다 부모의 값이 작다면

자식과 부모의 위치를 바꾸기 위해 True를 리턴해준다.

 

부모의 값이 더 크다면 정렬을 시킬 필요가 없으므로 False를 리턴해준다.

 

	else:
            if self.heap[left_child] > self.heap[right_child]:
                if self.heap[left_child] > self.heap[index]:
                    self.child_check = 1
                    return True
                else:
                    return False

 

만약 왼쪽 자식이 오른쪽 자식보다 크고, 부모보다 크다면

왼쪽 자식과 부모의 위치를 바꿔주면 되므로 

child_check에 1을 넣어주고 True를 리턴

            else:
                if self.heap[right_child] > self.heap[index]:
                    self.child_check = 2
                    return True
                else:
                    return False

 

오른쪽 자식만 부모보다 크다면

오른쪽 자식과 부모의 위치만 바꿔주면 되므로 

child_check에 2를 넣어주고 True를 리턴

 

        while self.shift_down(index):
            left_child = (index * 2) + 1
            right_child = (index * 2) + 2

            if self.child_check == 1:
                self.heap[index], self.heap[left_child] = self.heap[left_child], self.heap[index]
                index = left_child
            elif self.child_check == 2:
                self.heap[index], self.heap[right_child] = self.heap[right_child], self.heap[index]
                index = right_child

 

다시 left_pop으로 돌아와서

shift_down의 리턴 값이 True라면 반복문을 돌려준다.

 

child_check가 1이라면 왼쪽 자식과 부모의 위치를 바꿔주고

2라면 오른쪽 자식과 부모의 위치를 바꾼다.

 

 

아래는 max_heap을 구현한 전체 코드이다.

class Heap:
    # Heap을 구현하기 위한 배열을 선언
    def __init__(self):
        self.heap = []

    # 값을 넣어주고 shift_up 메소드를 통해 재정렬 
    def insert(self, data):
        self.heap.append(data)
        self.shift_up(len(self.heap) - 1)

    # 부모가 자식보다 작다면 부모와 자식의 위치를 바꿔준다.
    def shift_up(self, index):
        parent = (index - 1) // 2
        while index > 0 and self.heap[index] >= self.heap[parent]:
            self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
            index = parent
            parent = (index - 1) // 2


    # heap[0]을 pop하기 위한 메소드
    def left_pop(self):
        if not self.heap:
            return -1
            
        max = self.heap[0]
        current = self.heap[-1]
        self.heap[0] = current
        del(self.heap[-1])

        self.child_check = 0 
        index = 0
        
    # child_check가 1이라면 왼쪽 자식과 부모의 위치를 바꾸고, 2라면 오른쪽 자식과 부모의 위치를 바꾼다.
        while self.shift_down(index):
            left_child = (index * 2) + 1
            right_child = (index * 2) + 2

            if self.child_check == 1:
                self.heap[index], self.heap[left_child] = self.heap[left_child], self.heap[index]
                index = left_child
            elif self.child_check == 2:
                self.heap[index], self.heap[right_child] = self.heap[right_child], self.heap[index]
                index = right_child

        return max

    # 왼쪽 자식과 오른쪽 자식이 존재하는지 여부와 부모보다 크다면 True, 작다면 False를 반환한다.
    def shift_down(self, index):
        left_child = (index * 2) + 1
        right_child = (index * 2) + 2
            

    # 왼쪽 자식의 idx가 배열의 길이 이상이라면 자식이 없는 것이므로 False
        if left_child >= len(self.heap):
            return False

    # 왼쪽 자식이 존재하면서 오른쪽 자식의 idx가 배열의 길이 이상이라면 왼쪽 자식만 존재함
        elif right_child >= len(self.heap):
    
    # 왼쪽 자식이 부모보다 크다면 부모와 왼쪽 자식을 바꾸기 위해 child_check에 1을 넣어주고 True를 반환
            if self.heap[left_child] > self.heap[index]:
                self.child_check = 1
                return True
            else:
                return False

    # 자식이 둘 다 존재할 경우
        else:
            if self.heap[left_child] > self.heap[right_child]:
                if self.heap[left_child] > self.heap[index]:
                    self.child_check = 1
                    return True
                else:
                    return False
            else:
                if self.heap[right_child] > self.heap[index]:
                    self.child_check = 2
                    return True
                else:
                    return False