Heap-Sort

Heap-Sort(힙 정렬)은 Heap을 이용하여 정렬하는 알고리즘이다.
과정은 다음과 같다.

◾ 정렬할 배열을 Heap으로 변환한다.

◾ Heap에서 Root 노드를 삭제하면서 배열에 삽입한다.

◾ 삭제된 Root 노드를 배열의 다음 위치에 삽입한다. 이 과정을 Heap이 빈 Heap이 될 때까지 반복한다.

◾ 배열을 역순으로 정렬한다. 최소 힙에서는 오름차순으로 정렬되며, 최대 힙에서는 내림차순으로 정렬된다.

Heap-Sort의 시간 복잡도는 $O(n\,log\;n)$이다.

구현

from PriorityQueueBase import PriorityQueueBase

class HeapPriorityQueue(PriorityQueueBase):
    def parent(self, j):
        return (j - 1)// 2
    
    def left(self, j):
        return 2 * j + 1
    
    def right(self, j):
        return 2 * j + 2
    
    def has_left(self, j):
        return self.left(j) < len(self.data)
    
    def has_right(self, j):
        return self.right(j) < len(self.data)
    
    def swap(self, i, j):
        self.data[i], self.data[j] = self.data[j], self.data[i]
        
    def upheap(self, j):
        parent = self.parent(j)
        if j > 0 and self.data[j] < self.data[parent]:
            self.swap(parent, j)
            self.upheap(parent)
    
    def downheap(self, j):
        if self.has_left(j):
            left = self.left(j)
            small_child = left
            if self.has_right(j):
                right = self.has_right(j)
                if self.data[right] < self.data[left]:
                    small_child = right
            if self.data[left] < self.data[j]:
                self.swap(j, small_child)
                self.downheap(small_child)
                
    def __init__(self):
        self.data = []
        
    def __len__(self):
        return len(self.data)
    
    def add(self, key, value):
        self.data.append(self.item(key, value))
        self.upheap(len(self.data) - 1)
        
    def min(self):
        if self.is_empty():
            raise ValueError('Queue is Empty')
        item = self.data[0]
        return (item.key, item.value)
    
    def remove_min(self):
        
        if self.is_empty():
            raise ValueError('Queue is Empty')
            
        self.swap(0, len(self.data) - 1)
        item = self.data.pop()
        self.downheap(0)

Merging Two Heaps

Merging Two Heaps은 두 개의 Heap을 하나의 Heap으로 합치는 과정이다.
두 개의 Heap과 키 k가 주어졌을 때, 루트 노드가 k이고 두 개의 Heap이 하위 트리로 있는 새로운 Heap을 생성하는 과정은 다음과 같다.

◾ 키 k와 두 개의 Heap을 가지고, 새로운 Heap을 생성한다. 이때, 키 k가 Root 노드에 위치하고, 두 개의 Heap이 하위 트리로 위치한다.

◾ Downheap 과정을 수행하여 Heap-Order property을 유지한다.

Bottom-up Heap Construction

n개의 키를 가지고 Heap을 구성할 때, Bottom-up Construction을 사용하여 log n 단계에 걸쳐 Heap을 구성할 수 있다.

n개의 키를 가지고 구성한 Complete Binary Tree는 높이가 $log(n+1)$이다.

Bottom-up Construction은 Complete Binary Tree의 마지막 Level부터 Root 노드까지 순서대로 Downheap 과정을 수행한다. 이때, 한 단계를 수행할 때마다, 원소의 개수가 2배가 되는 Heap을 생성한다.

따라서, i번째 단계에서는 $2^{(i-1)}$개의 원소를 가지는 Heap을 생성하고, 이전 단계에서 생성된 Heap을 2개씩 병합하여 $2^{(i+1)}-1$개의 원소를 가지는 Heap을 생성한다.

총 log(n+1)단계를 수행하면, 마지막 단계에서 $2^{(log(n+1))}-1$개의 원소를 가지는 Heap을 생성할 수 있다.

Bottom-up Heap Construction의 시간 복잡도는 $O(n)$이다.