[파이썬 자료구조] 힙(Heap) - 개념, 최대힙, 최소힙, 코드 구현

힙이란?

→ 이진트리의 한 종류 (이진 힙 - binary heap 이라고도 부른다.)

1. 루트 (root) 노드가 언제나 최댓값 또는 최솟값을 가진다.
   1. 최대 힙 (max heap)
   2. 최소 힙 (min heap)
2. 완전 이진트리여야 함

 

→ 재귀적으로도 정의 된다. (어느 노드를 루트로 하는 서브트리도 모두 최대 힙)

→ 왼쪽과 오른쪽 자식을 비교하는 기준은 없다.

 

이러한 개념을 바탕으로 힙 연산을 코드 구현 해보자.

 

먼저 연산을 정의하자면

• init() - 빈 최대 힙을 생성
• insert(item) - 새로운 원소를 삽입
• remove() - 최대 원소 (root node) 를 반환 (그리고 동시에 이 노드를 삭제)

배열을 이용한 이진 트리의 표현

노드 번호 m을 기준으로

• 왼쪽 자식의 번호 : 2*m
• 오른쪽 자식의 번호 : 2*m +1
• 부모 노드의 번호 : m//2

완전 이진 트리이므로

• 노드의 추가/ 삭제는 마지막 노드에서만

 

그렇다면 최대힙에 원소를 삽입하는 insert 함수를 구현해 보겠다.

 

class MaxHeap:
    
    def __init__(self):
        self.data = [None]


    def insert(self, item):
        if len(self.data)==1:
            self.data.append(item)
        else:
            self.data.append(item)
            m=self.data.index(item)
            parent=m//2
            while self.data[m]>self.data[parent]:
                self.data[m],self.data[parent]=self.data[parent],self.data[m]
                m=parent
                parent=m//2
                if parent==0:
                    break

max=MaxHeap()
max.insert(13)
max.insert(14)

 

 

노드를 추가했으니 제거하는 코드도 만들어 보겠다.

 

remove() 함수 구현

class MaxHeap:
    
    def __init__(self):
        self.data = [None]

    def insert(self, item):
        if len(self.data)==1:
            self.data.append(item)
        else:
            self.data.append(item)
            m=self.data.index(item)
            parent=m//2
            while self.data[m]>self.data[parent]:
                self.data[m],self.data[parent]=self.data[parent],self.data[m]
                m=parent
                parent=m//2
                if parent==0:
                    break

    def remove(self):
        if len(self.data) > 1:
            self.data[1], self.data[-1] = self.data[-1], self.data[1]
            data = self.data.pop(-1)
            self.maxHeapify(1)
        else:
            data = None
        return data


    def maxHeapify(self, i):
        left = i*2
        right = i*2+1
        smallest = i
        if len(self.data)-1>=left and self.data[left]>self.data[smallest]:
            smallest=left

        if len(self.data)-1>=right and self.data[right]>self.data[smallest]:
            smallest=right

        if smallest != i:
            self.data[i],self.data[smallest]=self.data[smallest],self.data[i]
            self.maxHeapify(smallest)


max=MaxHeap()
max.insert(13)
max.insert(14)
max.insert(3)
max.insert(34)
print(max.data)
print(max.remove())

 

 

최대/최소 힙의 응용

1. 우선순위 큐(priority queue)
   1. enqueue 할 때 '느슨한 정렬'을 이루고 있도록 함 : O(logn)
   2. dequeue 할 때 최대값을 순서대로 추출: O(logn)
   3. 16강에서의 양방향 연결리스트 이용 구현과 효율성 비교
2. 힙 정렬 (heap sort)
   1. 정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입: O(logn)
   2. 삽입이 끝나면, 힙이 비게 될 때까지 하나씩 삭제: O(logn)
   3. 원소들이 삭제된 순서가 원소들의 정렬 순서
   4. 정렬 알고리즘의 복잡도: O(nlogn)