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;
};