Egbert Lin's Blog

“Life is not a race, but a journey to be savoured each step of the way” by Brian Dyson

Data Structures - HeapSort

Posted on Edited on In Disqus:

Basic programming - Heap Sort

Approach:

Heap is a complete binary tree. And, heap feature is that parent node must bigger than its child nodes. It also calls max-heap.

So, heapify() function ensures the max-heap principle. Get the index of left/right child easily by using the argument i (parent node). Then, find the child nodes which is bigger than their parent node and call swap().

If all of the elements are no heap priciple, heapify() function is not enough handling, so we need to write buildheap() function at the begining.
Buildheap() function scans all of the elements between parent node and child nodes and forms a max-heap.

Finally, we need to implement heap sort. We can always pop the root node because it is a largest element. Hence, use swap(arr, 0, i) to put root node to the tail of array. i is the the size of arrary - 1 and it will descending. Then, call heapify() function to make larger element moved to root and call swap() again until i is equal to zero.

Time complexity:
  • Best Case：Ο(nlogn)
  • Worst Case：Ο(nlogn)
  • Average Case：Ο(nlogn)

    • Space complexity: O(1)

    Stable/Unstable: Stable

    Source code

    Version 1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    #include <iostream>

    using namespace std;

    void swap(int arr[], int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    void heapify(int arr[], int n, int i){
        if(i >= n) return;
        int c1 = i * 2 + 1;
        int c2 = i * 2 + 2;
        int max = i;
        if(c1 < n && arr[c1] > arr[max]){
            max = c1;
        }
        if(c2 < n && arr[c2] > arr[max]){
            max = c2;
        }
        if(max != i){
            swap(arr, max, i);
            heapify(arr, n, max);
        }
    };

    void buildheap(int arr[], int n){
        int number = n - 1;
        int parent = (n - 1) / 2;
        for(int i = parent; i >= 0; --i){
            heapify(arr, n, i);
        }
    }

    void heapsort(int arr[], int n){
        buildheap(arr, n);
        for(int i = n - 1; i >=0; --i){
            swap(arr, 0, i);
            heapify(arr, i, 0);
        }
    }

    int main()
    {
        int arr[] = {2, 5, 3, 1, 10, 4};
        int n = sizeof(arr)/sizeof(arr[0]);
        cout << "Size of array:" << n << endl;
        heapsort(arr, n);
        
        for(int i = 0; i < n; ++i){
            cout << arr[i] << " ";
        }

        return 0;
    }