힙(Heap)과 힙 정렬(Heap sort) - 자료구조, 알고리즘, 파이썬

힙이라는 자료구조는 무엇일까.

한 노드(node)가 최대 2개의 자식 노드를 가지면서, 마지막 레벨을 제외한 모든 노드가 꽉 채워진 트리구조를 말한다.

모든 노드의 값이 각자의 자식 노드의 값보다 크거나 같은 것을 최대 힙(Max heap)이라한다.

모든 노드의 값이 각자의 자식 노드의 값보다 작거나 같은 것을 최소 힙(Min heap)이라한다.

힙은 최대 힙이거나 최소 힙이어야 한다.

또한, 마지막 레벨을 제외한 모든 노드가 꽉 채워진 완전이진트리(complete binary tree)이다.

이러한 힙 속성(최대 힙, 완전이진트리)를 만족하면 다음 그림처럼 트리구조가 완성된다.

힙은 완전이진트리 성질을 만족하기 때문에 1차원 배열로도 표현이 가능하다.

[100, 19, 36, 17, 3, 25, 1, 2, 7]

힙을 구현하기 위해선 다음과 같은 메소드들이 필요하다.

*힙의 성질을 만족하게끔 노드를 움직이는 heapify 메소드

heapify의 시간 복잡도는 최악의 경우 루트 노드에서 잎새 노드까지 값을 비교해야 하므로 트리의 높이에 의존적입니다.

값을 비교하거나 바꾸는 연산은 O(1)이므로 결과적으로 heapify의 시간 복잡도는 O(log n)이 됩니다.

*heapify 메소드를 보조하기 위해 노드의 왼쪽 노드, 오른쪽 노드를 찾아주는 메소드

*임의로 주어진 배열이 힙 성질에 만족하도록 바꾸어주는  buildheap 메소드.

잎새 노드를 가지지 않는 노드부터 차례대로 heapify를 수행합니다.

O(n)의 시간 복잡도로 만들 수 있습니다.

이러한 메소드들을 이용하여 힙을 구성한 후, 정렬할 수 있습니다.

heap sort의 방법은 다음과 같습니다.

1. 주어진 원소들로 최대 힙을 구성합니다.

2. 최대 힙의 루트 노드(=최댓값)와 말단노드(=현재배열의 마지막 요소)를 교환해줍니다.

3. 새로운 말단 노드는 앞으로의 연산에서 제외합니다.

4. 새로운 루트 노드에 대해 heapify를 진행하여 최대힙을 구성합니다.

5. 원소의 개수만큼 2, 3, 4을 반복 수행해줍니다.

오름차순으로 정렬하게 된다면 최대 값은 배열의 맨 뒤에 위치하게 됩니다. 최대 값인 루트 노드를 말단으로 옮겨주고 다음 연산에서 제외

함으로서 연산이 반복될수록 차곡차곡 배열의 뒤쪽으로 큰 수들이 이동하게 되어 정렬이 되는 구조입니다.

class Heap:
    def __init__(self):
        self.h = []
        self.currsize = 0
 
    def leftChild(self,i):
        if 2*i+1 < self.currsize:
            return 2*i+1
        return None
 
    def rightChild(self,i):
        if 2*i+2 < self.currsize:
            return 2*i+2
        return None
 
    def maxHeapify(self,node):
        if node < self.currsize:
            m = node
            lc = self.leftChild(node)
            rc = self.rightChild(node)
            if lc is not None and self.h[lc] > self.h[m]:
                m = lc
            if rc is not None and self.h[rc] > self.h[m]:
                m = rc
            if m!=node:
                temp = self.h[node]
                self.h[node] = self.h[m]
                self.h[m] = temp
                self.maxHeapify(m)
 
    def buildHeap(self,a):
        self.currsize = len(a)
        self.h = list(a)
        for i in range(self.currsize//2,-1,-1):
            self.maxHeapify(i)
 
    def getMax(self):
        if self.currsize >= 1:
            me = self.h[0]
            temp = self.h[0]
            self.h[0] = self.h[self.currsize-1]
            self.h[self.currsize-1] = temp
            self.currsize -= 1
            self.maxHeapify(0)
            return me
        return None
 
    def heapSort(self):
        size = self.currsize
        while self.currsize-1 >= 0:
            temp = self.h[0]
            self.h[0] = self.h[self.currsize-1]
            self.h[self.currsize-1] = temp
            self.currsize -= 1
            self.maxHeapify(0)
        self.currsize = size
 
    def insert(self,data):
        self.h.append(data)
        curr = self.currsize
        self.currsize+=1
        while (curr-1)//2 >= 0 and self.h[curr] > self.h[(curr-1)//2]:
            temp = self.h[(curr-1)//2]
            self.h[(curr-1)/2] = self.h[curr]
            self.h[curr] = temp
            curr = (curr-1)//2
 
    def display(self):
        print(self.h)