Heap Sort

Textbook

Description:

Example:

Note

Idea:

• Not stable
• In place
• Time: O(nlogn)

// Time: O(lg n)
void maxHeapify(vector<int> & nums, int i, int heap_size)
// Time: O(n)
void buildMaxHeap(vector<int> & nums)

Use priority_queue in C++ as heap

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

By default is Max heap,

priority_queue<int, vector<int>, greater<int> > is Min heap.

Code:

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

inline int parent(int i){
    return (i-1)/2;
}

inline int left_child(int i){
    return 2*i+1;
}

inline int right_child(int i){
    return 2*i+2;
}

// Time: O(lg n)
void maxHeapify(vector<int> & nums, int i, int heap_size){
    int l = left_child(i);
    int r = right_child(i);

    int largest;
    if(l<heap_size && nums[l]>nums[i]){
        largest = l;
    }
    else largest = i;

    if(r<heap_size && nums[r]>nums[largest]){
        largest = r;
    }
    if(largest != i){
        swap(nums[i], nums[largest]);
        maxHeapify(nums, largest, heap_size);
    }

}

// Time: O(n)
void buildMaxHeap(vector<int> & nums){
    int heap_size = nums.size();
    for(int i=(heap_size-1-1)/2; i>=0; --i){
        maxHeapify(nums, i, heap_size);
    }
}


// Time: O(n lg n)
void heapSort(vector<int> & nums){
    buildMaxHeap(nums);
    int heap_size=nums.size();
    for(int i=nums.size()-1; i>=1; --i){
        swap(nums[0], nums[i]);
        heap_size--;
        maxHeapify(nums, 0, heap_size);
    }
}

int main(){
    vector<int> input={3,4,2,5,6,7,2,3,3,8,9,23,43,22,1,23};

    for(auto e: input){
        cout<<e<<' ';
    } cout<<'\n';

    heapSort(input);

    for(auto e: input){
        cout<<e<<' ';
    } cout<<'\n';

}