Top_K問題，堆排序

Top_K問題

簡述：在大量資料中選出K個最大的或最小的。

以取K個最大數為例：

具體思路：

1. 将給定的資料的前K個元素壓入到vector空間，對這K個數進行向下調整建小堆;

2. 再将堆頂元素和數組的其他元素進行比較，當堆頂元素小于數組中所取元素時，将所取數組元素入堆;

3. 再進行調整，直到數組所有元素都依次進行比較。

//仿函數比較
template<class T>
struct Less
{
    bool operator()(const T& l, const T& r)
    {
        return l < r;
    }
};
template<class T>
struct Greator
{
    bool operator()(const T& l, const T& r)
    {
        return l > r;
    }
};

template<class T,class Compare >
class K_Heap
{
public:
    K_Heap()
    {}
    K_Heap(T* arr, size_t size, size_t k)
    {
        assert(k < size);
        _a.reserve(k);
        for (size_t i = ; i < k; ++i)
        {
            _a.push_back(arr[i]);
        }
        for (size_t i = (k - ) / ; i > ; --i)
        {
            AdjustDown(k, i);
        }
        for (size_t i = ; i < size; ++i)
        {
            if (_a[] < arr[i])
            {
                _a[] = arr[i];
                AdjustDown(k, );
            }
        }
        for (size_t i = ; i < k; ++i)
        {
            cout << _a[i] << " ";
        }
        cout << endl;
    }
protected:
    void AdjustDown(size_t k, size_t parent)
    {
        Compare com;
        size_t child = parent *  + ;
        while (child < _a.size())
        {
            if (child +  < _a.size() && com(_a[child+], _a[child]))
            {
                ++child;
            }
            if (com(_a[child], _a[parent]))
            {
                swap(_a[child], _a[parent]);
                parent = child;
                child = parent *  + ;
            }
            else
            {
                break;
            }
        }
    }
private:
    vector<T> _a;
};
           

堆排序：

具體思路：

1. 将給定的數組壓入vector中，對其進行向下調整調節為大堆或者小堆；

2.取出最小的數和最大數進行交換；

3.再次進行調整的時候元素的個數應該減一，不用算最後一個元素（因為最後一個不是最大的數就是最小的數）；

4.直到所有的數都依次進行了比較。

//堆排序
template<class T>
struct Less
{
    bool operator()(const T& l, const T& r)
    {
        return l < r;
    }
};
template<class T>
struct Greator
{
    bool operator()(const T& l, const T& r)
    {
        return l > r;
    }
};
template<class T, class Compare>
class Sort_Heap
{
public:
    Sort_Heap()
    {}
    Sort_Heap(T* arr, size_t size)
    {
        _a.reserve(size);
        for (size_t i = ; i < size; ++i)
        {
            _a.push_back(arr[i]);
        }
        for (int i = (size - ) / ; i >= ; --i)
        {
            AdjustDown(size, i);
        }
    }
    void AdjustDown(size_t size, size_t parent)
    {
        Compare com;
        size_t child = parent *  + ;
        while (child < size)
        {
            if (child +  < size && com(_a[child + ], _a[child]))
            {
                ++child;
            }
            if (com(_a[child], _a[parent]))
            {
                swap(_a[child], _a[parent]);
                parent = child;
                child = parent *  + ;
            }
            else
            {
                break;
            }
        }
    }
    void _Sort_Heap(size_t size)
    {
        size_t end = size - ;
        while (end > )
        {
            swap(_a[], _a[end]);
            AdjustDown(end, );
            --end;
        }
    }
    void Print()
    {
        for (size_t i = ; i < _a.size(); ++i)
        {
            cout << _a[i] << " ";
        }
        cout << endl;
    }
private:
    vector<T> _a;
};