[python] 자료구조 - 힙(Heap) / 우선순위 큐 (Priority Queue)

힙(Heap)

 

출처: https://en.wikipedia.org/wiki/Heap_(data_structure)

 

힙은 최대값과 최소값을 빠르게 찾기 위한 이진 트리다. 이진 탐색 트리(Binary Serach Tree)처럼 동일한 이진 트리라는 공통점이 있다. 하지만 트리와 힙은 다르다. 가장 큰 차이점은 힙의 경우 최대값이나 최소값이 루트 노드에 자리잡고 있다는 것이다. 또한 이진 탐색 트리의 경우 링크드 리스트 구조로 각 노드를 연결하는 반면 힙은 배열을 이용한다.

 

위 이미지의 구조가 트리였다면 level 2에 위치하는 3과 1은 왼쪽 노드에 존재해야한다. 하지만 힙은 삽입 데이터의 크기에 따라서 좌우 정렬을 하지 않는다. 목적 자체가 최소, 최대값을 빠르게 찾기 위함이기 때문에 최대값, 최소값을 루트 노드에 위치 시키는 것이 가장 중요하다. (위 이미지의 경우 최대 힙이므로 자식 노드는 부모 노드보다 작거나 같아야 한다.)  

 

트리의 경우 루트 노드가 정해지면 이를 기준으로 데이터가 나무의 가지처럼 뻗어 나간다. 반면 힙의 경우 추가되는 데이터는 배열 끝에 붙고, 그 값이 부모 노드 보다 큰지 작은지를 확인하면서 데이터의 위치를 스왑해준다.

 

우선순위 큐는 이러한 힙이라는 자료구조를 이용하여 구현한다.

 

 

 

출처 https://www.cs.cmu.edu/~adamchik/15-121/lectures/Binary%20Heaps/heaps.html

0. 어떤 구조를 활용해야 할까?

힙은 배열을 사용하고 있으므로 크기 비교를 위해서는 인덱스가 필요하다. 힙은 이진 트리다. 따라서 한 노드의 부모 노드는 노드의 인덱스를 2로 나눈 몫에 해당한다.

 

위 이미지에서 숫자 5의 인덱스는 7이다. 2로 나눈 몫은 3이다. 5의 부모 노드인 12의 인덱스는 3이다.

 

다음으로 한 노드의 자식노드는 왼쪽과 오른쪽 두 가지가 있다. 여기에도 간단한 규칙이 있다. 12의 인덱스는 3번이다. 12의 자식 노드인 17과 5의 인덱스는 각각 6과 7이다.

 

왼쪽 자식 노드 = 부모 노드 인덱스 * 2

오른쪽 자식 노드 = 부모 노드 인덱스 * 2 + 1

 

*단 루트 노드의 인덱스가 1부터 시작해야한다.

 

 

출처: https://www.geeksforgeeks.org/binary-heap/

 

위 이미지의 구조는 최소 힙(Min Heap)이다. 가장 작은 숫자인 1이 루트 노드에 자리잡는다. (빨간 숫자는 데이터의 인덱스를 의미한다.)

 

힙은 데이터가 왼쪽부터 차례대로 채워지는 구조다. 만약 6이 3보다 먼저 들어왔다면, 서로의 자리가 바뀌었을 것이다. 새로 들어오는 데이터가 루트 노드와 크기를 비교하고 그 다음으로 부모 노드 보다 큰지, 작은지를 비교한다.  

 

 

 

1. 만약 6번 자리에 0이라는 숫자를 추가하면 어떻게 될까?

배열의 크기가 커졌고 0이라는 데이터가 삽입되었다고 가정한다. 최소 힙이기 때문에 자식 노드는 부모 노드 보다 크거나 같아야한다는 조건이 있다. 따라서 1의 부모 노드는 1보다 작거나 같아야한다.

 

(1). 6번 자리의 부모 노드는 2번이다 0이 6보다 더 작으므로 위치를 교체한다. 

(2). 이제 0의 부모 노드는 0번에 위치한 1이다.

(3). 0은 1보다 작다. 한 번 더 스왑한다.

(4). 0번 자리에 0이 자리 잡는다. 

 

[0][3][1][5][9][8][6] 모양의 배열이 될것이다.

 

 

만약 4라는 숫자가 삽입 된다면 6번 인덱스에 자리를 잡고, 다음으로 부모 노드와 크기를 비교할 것이다. 숫자 4는 6보다 작으므로 2번 자리로 올라가게 될 것이다. 4는 1보다 크므로 스왑이 끝난다.

 

2. 데이터를 삭제하는 경우

힙은 최소, 최대값을 빠르게 찾기 위한 구조이므로 데이터를 삭제 하는 경우가 최소, 최대 값을 삭제하는 경우다. 따라서 데이터 삭제시 루트 노드를 삭제하고 최대 힙, 최소 힙 여부에 따라서 데이터들을 스왑해준다. 

 

삭제의 경우 루트 노드를 삭제하므로 0번 인덱스의 데이터를 삭제한다. 이때 루트 노드의 자리가 비는데 보통은 배열 마지막에 위치한 데이터를 루트 노드로 이동시킨다. 다음 단계는 루트 노드의 크기를 비교하며 조건을 만족할 때까지 데이터들의 인덱스를 교체해준다. 

 

 

아래 코드는 부모, 자식의 인덱스 규칙을 활용하기 위해서 인덱스 0을 None으로 고정시켰다. 따라서 루트 노드의 인덱스는 항상 1이다.

#Max Heap
class Heap:
    def __init__(self):
        self.heap_array = []
        self.heap_array.append(None)
    
    # for delete loop
    def move_down(self, index_id):
        left_id = index_id * 2
        right_id = index_id * 2 + 1
        
        # case 1 no child
        if left_id >= len(self.heap_array):
            return False
        
        # case 2 one child
        elif right_id >= len(self.heap_array):
            if self.heap_array[left_id] > self.heap_array[index_id]:
                return True
            else:
                return False
            
        # case 3 two child
        else:
            if self.heap_array[left_id] > self.heap_array[right_id]:
                if self.heap_array[left_id] > self.heap_array[index_id]:
                    return True
                else:
                    return False
            else:
                if self.heap_array[right_id] > self.heap_array[index_id]:
                    return True
                else:
                    return False
            
        
    
    def delete(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]
        
        index_id = 1
        while self.move_down(index_id):
            left_id = index_id * 2
            right_id = index_id * 2 + 1
            
            if self.heap_array[left_id] > self.heap_array[right_id]:
                if self.heap_array[left_id] > self.heap_array[index_id]:
                    temp = self.heap_array[left_id]
                    self.heap_array[left_id] = self.heap_array[index_id]
                    self.heap_array[index_id] = temp
                    index_id = left_id
            else:
                if self.heap_array[right_id] > self.heap_array[index_id]:
                    temp = self.heap_array[right_id]
                    self.heap_array[right_id] = self.heap_array[index_id]
                    self.heap_array[index_id] = temp
                    index_id = right_id
        
        return returned_data
            
    
    # for insert loop
    def move_up(self, index_id):
        if index_id == 1:
            return False
        
        parent_id = index_id // 2
        if self.heap_array[parent_id] < self.heap_array[index_id]:
            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)
        index_id = len(self.heap_array) -1
        
        while self.move_up(index_id):
            parent_id = index_id // 2
            
            temp = self.heap_array[parent_id]
            self.heap_array[parent_id] = self.heap_array[index_id]
            self.heap_array[index_id] = temp
            index_id = parent_id
            
            """
            self.heap_array[parent_id], self.heap_array[index_id] =\
            self.heap_array[index_id], self.heap_array[parent_id]
            """
        
        return True

#Test Code
heap = Heap()
heap.insert(10)
heap.insert(8)
heap.insert(5)
heap.insert(4)
heap.insert(20)
print(heap.heap_array)

heap.delete()
print(heap.heap_array)