Heap 구조 및 파이썬 구현

Heap이란 무엇인가?

---

Heap은 우선순위 큐를 구현하기 위해 고안된 자료구조다. 우선순위 큐는 일반적인 큐의 선입선출 동작과는 다른 동작을 한다. 늦게 들어온 값이라도, 우선순위가 높으면 먼저 나오는 기능이 구현된 자료구조다. 

 

Heap은 어떻게 구현하는가?

---

Heap은 크게 배열, 링크드리스트, 트리로 구현할 수 있다. 그렇지만 트리로 구현하는 것이 가장 좋은 것으로 알려져 있다. 

위처럼 배열로 구현된 Heap이 있다고 가정해본다. 이 때, Heap에 삽입을 할 때, 자기가 들어가야 할 자리를 탐색해야하기 때문에 탐색에만 O(n) 시간이 필요하다. 중간에 삽입 시, 뒷쪽에 있는 배열들을 늘려주고 한 칸씩 이동해주어야 한다. 삭제를 할 경우, 가장 앞에 있는 인덱스를 삭제할 경우 한 칸씩 땡겨야 하기 때문에 O(n) 시간 복잡도가 필요하다.

링크드리스트로 구현 시, 삽입 하는 연산 자체는 O(1)이 필요하지만 탐색하는데 O(n)의 시간이 걸린다. 그렇지만 삭제는 가장 우선순위가 높은 것을 지워주면 되기 때문에 O(1)이 필요하다.

반면에 트리로 Heap을 구현할 경우 시간복잡도는 삽입, 삭제 모두 O(logn)의 시간복잡도가 필요하다. 이 시간복잡도가 되는 이유는 삽입과 삭제 시, 각각 트리의 높이만큼만 살펴보면 되기 때문이다. 이런 시간복잡도의 이유로 Heap은 트리로 구현하게 된다. 

 

Tree로 구현한 Heap의 특성

---

Tree로 구현한 Heap에 대해 먼저 두 가지 정의를 하고 시작한다.

1. 모든 부모노드는 자식노드보다 우선순위가 크거나 같다. (크다, 작다는 최소힙, 최대힙이냐에 따라 변경)
2. Heap은 완전이진트리의 형태를 가진다.

1번 정의를 좀 더 명확하게 알아야 하는데, 1번 정의는 자식 노드와 부모 노드 관계에 대해서만 명확하게 이야기를 하는 것이다. 예를 들어 자식 노드끼리는 어떤 것이 우선순위가 높은지에 대해 정의지지 않는다. 위 이미지처럼 표현할 수 있다.

또한, 나와 같은 항렬의 부모노드의 자식 노드와의 대소 관계 역시 알 수 없다. 왜냐하면 자식 노드에서의 우선순위에 대한 정의가 없기 때문이다. 예를 들어 위 이미지와 같은 경우가 있다. 주황색 노드끼리를 비교하면 어떤 말인지 명확히 알 수 있다. 

Tree로 구현한 Heap을 구현하기 위해서는 링크드리스트보다는 배열이 선호된다. 왜냐하면 Heap의 연산 과정에는 마지막 위치에 값을 넣는 경우가 있는데, 링크드리스트는 탐색까지 O(n)이 걸리기 때문에 배열로 완전이진트리 형태의 Heap을 구현한다.

 

 

Heap의 삽입 연산

---

먼저 루트 노드는 1번 인덱스로 고정한다. 이는 부모노드, 자식노드 간의 연산을 수월하게 하기 위함이다. 이 후의 Heap의 삽입 연산은 다음과 같은 과정으로 구성된다.

1. 배열의 가장 마지막 위치에 값을 삽입한다. (현재 값이 가장 작다고 가정한다)
2. 부모노드와 비교하며, 자기 자리를 찾아간다.

좀 더 자세하게는 다음과 같이 설명 가능하다

1. 배열의 가장 마지막 위치에 값을 삽입한다. (현재 값이 가장 작다고 가정한다)
2. 반복문을 수행하며 부모노드와 비교한다. 
3. 부모노드보다 우선순위가 떨어지면 반복문을 종료한다
4. 부모노드보다 우선순위가 높으면 부모노드의 값을 자식노드에 저장한다. 현재 자식 노드의 위치를 부모 노드로 업데이트 해준다.
5. 현재 자식 노드 위치에 자식 값을 업데이트 해준다.
6. 상세한 코드는 다음과 같다.

def heappush(tree,value) :
    tree.append(value)

    #현재 부모 노드
    node = len(tree) - 1
    #현재 자식 노드 위치
    last_idx = node

    #노드가 1보다 클 때까지 탐색한다.
    while node > 1 :

        # 현재 노드를 부모 노드로 바꿔줌.
        node //= 2

        #부모 노드가 크면, 부모 노드를 자식 노드에 저장함.
        # 현재 자식 노드 위치를 부모 노드로 업데이트
        if tree[node] > value :
            tree[last_idx] = tree[node]
            last_idx = node
        #부모 노드보가 작을 경우, 반복문 종료
        else :
            break

    #현재 자식 노드 위치에 값 업데이트.
    tree[last_idx] = value
    return

 

Heap의 삭제 연산

---

Heap의 삭제 연산은 루트 노드에 있는 값을 삭제하고 출력해주는 역할을 수행한다. 값을 삭제해준 후에는 다시 한번 힙형태로의 정렬이 필요한데, 이 때는 힙의 가장 마지막에 있는 값을 루트 노드로 옮겨준 후 자기 자리를 찾는 방식으로 이루어진다. 삭제 연산은 자식 노드가 없는 경우도 있기 때문에 삽입 연산에 비해 조금 복잡하다.

삭제 연산을 구현하기 위해 먼저 편의를 위해 자식 노드끼리 우선순위를 비교해서, 우선순위가 높은 자식 노드의 위치를 반환하는 함수를 정의해준다. 아래 함수는 최소힙을 구현하는데 사용한 함수다. 최대힙의 경우 대소관계가 반대로 바뀌게 된다. 내용은 다음과 같다

1. 트리의 전체 길이가 오른쪽 자식노드의 위치보다 크다면(자식 노드가 둘다 존재한다면), 대소 비교를 해서 값을 리턴한다.
2. 트리의 전체 길이가 왼쪽 자식노드의 위치와 동일하다면(왼쪽 자식노드만 존재한다면), 왼쪽 자식 노드의 값을 리턴한다
3. 그렇지 않을 때(자식 노드가 없다면), -1을 리턴한다.

def get_priority(tree,node) :
    if len(tree)-1 >= node*2 + 1 :
        if tree[node*2] > tree[node*2 + 1]:
            return node*2 + 1
        else :
            return node*2
    elif len(tree)-1 == node*2 :
        return node*2
    else :
        return -1

위의 함수가 정의되었다면, 아래 로직으로 삭제 연산을 구현할 수 있다.

1. 현재 Heap이 비어있으면 리턴한다.
2. 루트 노드의 값을 반환값에 저장한다.
3. 힙의 마지막 값을 저장하고, 시작 노드를 루트 노드로 설정한다.
4. 아래 반복문을 반복한다
   4-1.  자식 노드가 없다면 반복문을 종료한다.
   4-2.  자식 노드가 있다면, 우선순위가 작은 녀석과 비교한다. 마지막 값이 우선순위가 작은 녀석보다 작다면 반복문을 종료한다.
   4-3. 그렇지 않다면 현재 노드의 값과 자식 노드의 값을 바꿔주고, 마지막 값의 위치를 현재 자식 노드로 업데이트 해준다.
5. 마지막 값의 위치에 마지막 값을 저장한다
6. 힙의 제일 마지막에 있는 값을 삭제하고, 1번에서 저장해둔 값을 반환한다.

def heappop(tree) :
    if len(tree) == 1 :
        return 0

    return_value = tree[1]
    last_data = tree[-1]
    node = 1

    while 1 :

        #우선순위가 높은 자식 노드를 찾는다.
        pri_node = get_priority(tree,node)

        #만약 자식 노드가 없으면 끝.
        if pri_node == - 1 :
            break

        #자식노드가 있고, 나보다 우선 순위가 높으면
        if last_data > tree[pri_node] :
            # 현재 노드에 자식 노드 값을 업데이트
            tree[node] = tree[pri_node]
            # 현재 노드 주소를 자식 노드로 업데이트
            node = pri_node
        else :
            break
    tree[node] = last_data
    tree.pop()
    return return_value

  

Heap Class 전체 코드

내가 구현한 Heap Class 전체 코드는 아래와 같다. 여기에 추가 되어야 할 함수는 Heapfy 함수인데, Heapfy는 추후 업데이트 예정이다. 완벽한 코드는 아니고, 다른 분들이 짜신 코드가 더 짜임새 있고 효율성이 있을 것이기 때문에 아래 코드는 자료구조를 처음 하는 사람들이 참고하는 정도만으로 사용하면 좋을 것 같다. 

class nheap(object) :

    def __init__(self):
        self.hq = [0]

    def get_priority(self, node):
        if len(self.hq) - 1 >= node * 2 + 1:
            if self.hq[node * 2] > self.hq[node * 2 + 1]:
                return node * 2 + 1
            else:
                return node * 2
        elif len(self.hq) - 1 == node * 2:
            return node * 2
        else:
            return -1

    def heappop(self):
        if len(self.hq) == 1:
            return 0

        return_value = self.hq[1]
        last_data = self.hq[-1]
        node = 1

        while 1:
            pri_node = self.get_priority(node)

            
            if pri_node == - 1:
                break

            
            if last_data > self.hq[pri_node]:
                self.hq[node] = self.hq[pri_node]
                node = pri_node
            
            else:
                break
        self.hq[node] = last_data
        self.hq.pop()
        return return_value





    def heappush(self,value) :
        self.hq.append(value)
        node = len(self.hq) - 1
        last_idx = node

        while node > 1 :
            node //= 2

            if self.hq[node] > value :
                self.hq[last_idx] = self.hq[node]
                last_idx = node
        
            else :
                break
        
        self.hq[last_idx] = value
        return

 

 

Heap 정렬

위의 Heap 자료구조를 이용한 정렬을 Heap 정렬이라고 한다. Heap 정렬은 오름차순, 내림차순 정렬에 따라 필요한 Heap구조가 조금 바뀌게 된다. 내림차순으로 정렬할 경우, 큰 값부터 먼저 나와야 하기 때문에 최대힙을 사용하여 정렬한다. 반면 오름차순 정렬은 최소힙을 사용하여 정렬하게 된다. 

위 예시를 보면 확실히 알 수 있다. 오름차순으로 정렬할 때, 최소힙으로 자료구조를 형성한 후 루트 노드의 값을 꺼내주어 그 값을 저장하기만 하면 된다. 위의 이미지에서는 최소힙이 구현되어있고, 루트노드를 반복해서 빼게 될 경우 값은 1 → 2 → 4 → 7 → 9으로 나오게 된다. 

Heap정렬은 삭제 연산을 통해 구현이 되는데, 앞서 이야기 했듯이 삭제 연산에는 O(logn)의 시간복잡도가 필요하다. 그런데 n개의 요소에 대해 진행해야 하기 때문에 시간복잡도는 O(nlogn)으로 정렬할 수 있다.