Heap Sort

Heap sort is one of traditional sorting algorithms with time complexity $\mathcal{O}(n\ln n)$. After reading this article, you will be able to build a left-justified binary tree and implement heap sorting algorithm. We first defined some terms that will be used later.

Definition (Balanced tree) A binary tree of depth $n$ is balanced if all the nodes at depth $0$ through $n-2$ have two children.

That is, for any two leaves in the tree the difference is at most 1. We can see some examples for balanced trees and imbalanced trees.

Definition (Left-justified binary tree) A binary tree is left-justified if all the leaves are at the same depth and all the leaves at depth $n+1$ are to the left of all nodes at depth $n$.

The following figures illustrates the left justified tree:

In order to implement heap sorting algorithm, we should first build a binary max-heap (min-heap) tree which is a left-justified balanced tree and whose parent nodes are always larger (smaller) than its children nodes. We can use an array to represent this binary heap tree since it is left-justified. Note that the children of node $i$ is always $2i+1$ and $2i+2$. The following figure shows a binary heap tree and its array form.

In order to maintain the heap property, we introduce a max-heapify procedure which takes an array $A$ and its index $i$. We assume the left and right subtrees of index $i$ are already max-heaps. The procedure lets the value $A[i]$ float down in the max-heap so that the subtree rooted at index $i$ becomes a max-heap. The max-heapify procedure is demonstrated as followed. Note that at each step, we swap the value of index $i$ with the value of child node with larger value.

With max-heapify procedure, we can build a binary heap tree from scratch. One important property is that the elements in the subarray $A[\left\lfloor \frac{1}{n}\right\rfloor: n-1]$ are leaves. So we can actually apply max-heapify procedure from the index $\left\lfloor \frac{1}{n}-1\right\rfloor$ to $0$ and a binary heap tree will be obtained.

After the tree is built, we can start to sort the array $A$. We can obtain the largest value in the array is the value of the root. At the first step, we can swap the value between the root and the last element, and then perform max-heapify on the array $A[0:n-2]$. At the $i^{\text{th}}$ step, we swap the value between the root and $n-i^{\text{th}}$ element and perform max-heapify on the array $A[0:n-i-1]$. We can repeatedly perform this algorithm until we traverse all the in the array. Finally, the resulting array will be perfectly sorted.

The heap sort algorithm is implemented in C++ as followed:

#include                                                                                                                       
#include  $using namespace std;

void swap(int &a, int &b);
void max_heapify(int* array, int idx, const int array_len);
void build_heap(int* array, const int array_len);
void print_array(const int* array, const int array_len);
void heap_sort(int* array, const int array_len);

int main(){
    
    int* array;
    int size;
    cout << "Array size: " << endl;
    cin >> size;
    array = new int[size];
    for (int idx=0; idx > array[idx];
    }
    
    // 1. build heap
    build_heap(array, size);
    cout << "Build heap binary tree: " << endl;
    print_array(array, size);
    
    // 2. heap sort
    heap_sort(array, size);
    cout << "After heap sort: " << endl;
    print_array(array, size);
    
    return 0;
}


void swap(int &a, int &b){
    int tmp = a;
    a = b;
    b = tmp;
}

void print_array(const int* array, const int array_len){
    for (int idx=0; idx array[right_idx]) \
                        ? left_idx \
                        : right_idx;
        }   
        else if (left_idx array[idx]){
            swap(array[child_idx], array[idx]);
            idx = child_idx;
        }
        else{ break; }
    }
}

void build_heap(int* array, const int array_len){
    for (int idx=array_len/2-1; idx>=0; --idx){
        max_heapify(array, idx, array_len);
    }
}$

Algorithm Notes

搜尋此網誌

Heap Sort

留言

張貼留言