堆排序

堆排序基本思想

堆排序是利用堆来进行排序的一种算法，其平均复杂度为Ｏ(nlogn)。要理解堆排序，首先要知道堆的插入和删除操作。由于堆的特性，堆顶的元素一定是比其他元素大（或者小），因此只要每次将堆顶的元素取出，删除该元素，然后调整堆，直到堆的大小为０。在这个过程中，取出的元素就会是有序的。在下面的排序中，我将用大顶堆实现降序，用小顶堆实现升序。

c++ 代码实现堆排序

#include <iostream>
#include <vector>
using namespace std;


class Heap{
public:
    vector<int> nums;
    int size;
    Heap(): size(0){}
    virtual ~Heap(){
        nums.clear();
    }

    int get_val_index(int val){
        int index = 0;
        while(index < size){
            if(val == nums[index])
                break;
            ++index;
        }
        return index;
    }

    void show_heap(){
        for (int i = 0; i < size ; ++i) {
            cout<<nums[i]<<" ";
        }
        cout<<endl;
    }
    virtual void filter_down(int start, int end){};

    virtual void filter_up(int start){};

     void insert_val(int x){
        nums.push_back(x);
        ++size;
        filter_up(size - 1);
    };

    void delete_val(int x){
        int index = get_val_index(x);
        nums[index] = nums[size-1];
        --size;
        filter_down(index, size - 1);
    };




};

class MaxHeap:public Heap{
public:
    MaxHeap():Heap(){}

    void filter_down(int start, int end){
        int _val = nums[start];
        int child_index = 2*start + 1;
        int curr_index = start;

        while(child_index <= end){
            if(child_index+1 <= end && nums[child_index+1] >= nums[child_index])
                ++child_index;
            if(nums[child_index] > _val){
                nums[curr_index] = nums[child_index];
                curr_index = child_index;
                child_index = 2* curr_index + 1;
            }
            else
                break;
        }
        nums[curr_index] = _val;
    }
    

    void filter_up(int start){
        int parent_index = (start - 1) / 2;
        int _val = nums[start];
        int curr_index = start;

        while(curr_index > 0){
            if(nums[parent_index] < _val){
                nums[curr_index] = nums[parent_index];
                curr_index = parent_index;
                parent_index = (curr_index - 1) / 2;
            }
            else
                break;
        }
        nums[curr_index] = _val;
    }


};



class MinHeap:public Heap{
public:
    MinHeap():Heap(){}

    void filter_down(int start, int end){
        int _val = nums[start];
        int child_index = 2*start + 1;
        int curr_index = start;

        while(child_index <= end){
            if(child_index+1 <= end && nums[child_index+1] < nums[child_index])
                ++child_index;
            if(nums[child_index] < _val){
                nums[curr_index] = nums[child_index];
                curr_index = child_index;
                child_index = 2* curr_index + 1;
            }
            else
                break;
        }
        nums[curr_index] = _val;
    }
    

    void filter_up(int start){
        int parent_index = (start - 1) / 2;
        int _val = nums[start];
        int curr_index = start;

        while(curr_index > 0){
            if(nums[parent_index] > _val){
                nums[curr_index] = nums[parent_index];
                curr_index = parent_index;
                parent_index = (curr_index - 1) / 2;
            }
            else
                break;
        }
        nums[curr_index] = _val;
    }

    
};

class HeapSort{
public:
    vector<int> Sort(vector<int> &n, bool reverse= false){
        //# 默认升序
        //# 降序采用大顶堆
        vector<int> ans;
        if(reverse){
            MaxHeap maxheap;
            Heap* heap = &maxheap;
            return Sort(heap, n);

        }
        else{
            MinHeap minheap;
            Heap* heap = &minheap;
            return Sort(heap, n);

        }

    }

    vector<int> Sort(Heap* heap, vector<int> &n){

        vector<int> ans;
        for (int i = 0; i < n.size() ; ++i) {

            heap->insert_val(n[i]);
        }

        while(heap->size){
            ans.push_back(heap->nums[0]);
            heap->delete_val(heap->nums[0]);

        }

        return ans;
    }
};

void show_array(vector<int> nums){
    for (int i = 0; i < nums.size() ; ++i) {
        cout<<nums[i]<<" ";
    }
    cout<<endl;
}

int main() {

    MaxHeap max_heap;
    vector<int> n = {90,12,300,28,9,12,0};

    cout<<"排序之前..."<<endl;
    show_array(n);
    HeapSort heapsort;
    cout<<"升序..."<<endl;
    show_array(heapsort.Sort(n));
    cout<<"降序..."<<endl;
    show_array(heapsort.Sort(n, true));

    return 0;
}