Heap Sort

Heap이란, complete binary tree를 기본으로 하는 자료구조이며, 다음의 heap property를 만족시킵니다.

Max Heap Property

• Root를 제외한 모든 node의 index i에 대해서 $A[PARENT(i)]\ge A[i]$를 만족해야함.
• A[1]이 tree의 root임을 가정한다.
• Parent of $A[i] = A[\lfloor{i/2}\rfloor]$
• Left child of $A[i] = A[2i]$
• Right child of $A[i] = A[2i+1]$

Min Heap Property

• Root를 제외한 모든 node의 index i에 대해서 $A[PARENT(i)]\le A[i]$를 만족해야함.
• 나머지 property는 max heap property와 동일함.

Heapify

알고리즘을 코드로 직접 설명하겠습니다.
코드는 이곳에서 확인할 수 있습니다.

template <class T>
class MaxHeap{
public:
        MaxHeap();
        MaxHeap(int);//constructor
        void Push(const T&e);
        void Pop();
        bool IsEmpty(){return heapSize == 0;}
        T Top(){
                return heap[1];
        }
private:
        int heapSize; // # of elements in heap
        int capacity; // size of the array heap
        T *heap; // element array
template <class T2>
friend ostream& operator<<(ostream&, MaxHeap<T2>&);
};

먼저 MaxHeap class에 대한 declaration이고, 핵심적인 method는 Push & Pop입니다. Push/Pop method 내부에서 heapify를 수행하도록 구현되어있습니다. Member variable은 heap의 size와 capacity에 대한 content입니다.

template <class T>
void MaxHeap<T>::Push(const T& e){
        if(heapSize == capacity){
                ChangeSize1D(heap, capacity + 1, 2*capacity +1);
                capacity *= 2;
        }
        int currentNode = ++heapSize;//미리 자리 확보
        /* 핵심적인 heapify */
        while(currentNode != 1 && heap[currentNode/2]<e){//부모 노드로 이동
                heap[currentNode] = heap[currentNode/2];
                currentNode /= 2;
        }
        heap[currentNode] = e;
}

Push에서 핵심적인 heapify 아래의 while문이 heapify에 대한 부분으로 new node와 new node의 parent와 비교하여 new node가 더 큰 경우, parent를 new node의 position에 assign하는 방식입니다.
이후 new node의 position을 확인하면 해당 위치에 new node를 assign합니다.

template <class T>
void MaxHeap<T>::Pop(){
        if(IsEmpty()) throw "Heap is empty. Cannot delete";
        heap[1].~T();//최대 원소 삭제
        //히프의 마지막 원소 제거
        T lastE = heap[heapSize--];
        //tricle down
        int currentNode = 1; //루트
        int child = 2;
        while(child<=heapSize)
        {		/* child를 currentNode의 큰 자식으로 설정 */
                if(child < heapSize && heap[child] < heap[child+1])child++;
                /* currentNode에 last E를 삽입할 수 있는가? */
                if(lastE>=heap[child]) break;//yes
                /* no */
                heap[currentNode] = heap[child]; /* 자식이 부모 자리로 이동 */
                currentNode = child; child*=2;   /* 비교할 레벨을 한단계 내려감 */
        }
        heap[currentNode] = lastE; /* last element를 assign */
}

Pop은 root node를 제거합니다. 즉, 가장 큰 element를 제거하는 method입니다.
Pop도 Push와 마찬가지로 heapify를 수행하게 됩니다.
Root node의 index를 currentNode에 assign한 뒤, 기존 root의 children 둘 중 큰 child와 heap의 last element를 비교하여 child가 더 크면 child를 root로 assign합니다. 다음으로 currentNode의 index를 child로 child의 index를 child*2로 변경합니다. 이 과정을 child가 더 heapSize보다 작지 않거나, last element가 child보다 큰 경우가 발생할때까지 수행합니다.
위의 maxheap을 사용한 예시 코드가 아래와 같습니다.

int main(){
  MaxHeap<int> H(3);
  H.Push(15); H.Push(14); H.Push(21); H.Push(2);
  H.Push(10); H.Push(20);

  cout << H;
  while(!H.IsEmpty()){
    cout << H.Top() << " "; 
    H.Pop();
  }
  cout << endl;
}

Complexity Analysis

Build max heap: $O(n)$
For loop: $n-1$ times
Exchange elemtns: $O(1)$
Max-heapify: $O(lgn)$
Total: $T(n)=O(nlgn)$