模拟实现堆+堆的应用

堆数据结构是一种数组对象，它可以被看作一颗完全二叉树的结构（数组是完全二叉树），堆是一种静态结构。
堆分为最大堆和最小堆。
最大堆：每个父结点都大于孩子结点。
最小堆：每个父结点都小于孩子结点。

堆的优势：效率高，可以找最大数最小数，增删的时间复杂度为lgN，快
怎么找最后一个叶子结点？
找到最后一个叶子结点（左孩子为空就是叶子结点），由于堆是静态结构，所以我们要通过计算下标的方法找，计算它的孩子是否超出了数组范围。

下图就是一个堆（以下举例都会用这个堆）

堆的基本实现

我们先建立一个最大堆

首先，堆的成员应该是一个数组，但是这个数组不能是固定的大小，因为我们要实现堆的插入删除，所以我们可以用库中的vector来创建数组。
即vector<T> _a;

构造函数
首先我们要写一个无参的构造函数，因为系统不会自动生成无参的构造函数，无参的构造函数刚开始堆是空的，不需要做任何事。

Heap()
{}

我们还需要写一个带参数的构造函数
给一个一定大小的数组。
我开空间，我们开空间用reserve()，因为size是一定的，如果用resize也可以但是我们就多初始化了一次。
然后逐一的用循环插入元素，
建堆，建堆的思想是：先找到最后一个非叶子结点，然后向下调整，在找到倒数第二个非叶子结点，向下调整，直到找到根节点。

Heap(T* a, size_t n)
    {
        _a.reserve(n);//开空间
        for (size_t i = 0; i < n; ++i)
        {
            _a.push_back(a[i]);

        }
        //建堆,找最后一个非叶子节点
        for (int i = (_a.size() - 2) / 2; i >= 0; --i)
        //不用size_t，因为i在这可能等于0
        {
            AdjustDown(i);
        }
    }

向下调整AdjustDown()

//向下调整
    void AdjustDown(int root)
    {
        int parent = root;
        int child = parent * 2 + 1;//默认为左孩子
        while (child < _a.size())
        {
            //选出大孩子
            if (child+1 < _a.size() && _a[child + 1] > _a[child])
            {
                ++child;
            }
            //如果孩子大于父亲则交换，否则跳出循环
            if (_a[child] > _a[parent])
            {
                swap(_a[child], _a[parent]);//值交换
                parent = child;
                child = parent * 2 + 1;
            }
            else
            {
                break;
            }
        }
    }

向上调整AdjustUp()
向上调整的思想和向下调整的思想是相同的
但在这里我们需要注意的是循环的结束条件：

while(child>0)
//while(parent>=0)
这两个我们只能使用第一个，因为父亲的计算方法为(child-1)/2，所以父亲不会为负数，从而导致程序死循环。

//向上调整
    void AdjustUp(int child)
    {
        int parent = (child - 1) / 2;
        while (child > 0)
        {
            if (_a[child] > _a[parent])
            {
                swap(_a[parent], _a[child]);
                child = parent;
                parent = (child - 1) / 2;
            }
            else
            {
                break;
            }
        }

    }

插入元素Push
堆的插入元素就在最后插入，所以我们在最后插入元素之后，向上调整即可

    void Push(const T&x)
    {
        _a.push_back(x);
        AdjustUp(_a.size() - 1);
    }

删除元素Pop
最大堆的删除元素，是删除最大的元素。
如图

我们不能直接删除19
原因：
1，vector不提供pop_front
2，如果直接删除19，那我们整个堆就会乱掉，重新构造这个堆的话，代价太大。

所以我们可以先将第一个结点和最后一个结点进行交换，然后删除最后一个结点，然后再进行向下调整。
代码实现如下：

//删除最大数
    void Pop()
    {
        assert(!_a.empty());
        swap(_a[0], _a[_a.size() - 1]);
        _a.pop_back();
        AdjustDown(0);

    }

取第一个元素Top()
堆的Top()实现相对简单一些，返回_a[0]。

//取顶元素
    T& Top()
    {
        assert(!_a.empty());
        return _a[0];
    }

判断它是否为最大堆
判断这个堆是否为最大堆，我们有两种方法可以解决
1，递归。
2，非递归。
我们先来看一下递归：

    bool IsHeap()
    {
        return _IsHeap(_root);//递归
    }
    bool _IsHeap(int root)
    {
        if (root >= _a.size())//不存在,是大堆
            return true;
        int left = root * 2 + 1;
        int right = root * 2 + 2;
        if (left < _a.size())
        {
            if (_a[left] > _a[root])
            {
                return false;
            }
            if (right < _a.size())
            {
                if (_a[right] > _a[root])
                {
                    return false;
                }
            }
        }
        return _IsHeap(left) && _IsHeap(right);

    }

非递归：

bool IsHeap()
    {
        //非递归
        for (size_t i = 0; i <= (_a.size() - 2) / 2; i++)
        {
            int left = i * 2 + 1;
            int right = i * 2 + 2;
            //最后一个非叶子结点左孩子一定存在，但是右孩子不一定存在
            if (_a[i] < _a[left] || (right < _a.size() && _a[i] < _a[right]))
            {
                return false;
            }
            return true;
        }

    }

堆的应用

1，优先级队列
（谁的优先级高（看具体场景）谁先出）
用堆实现

template<class T, class Compare = Greater<int>>
class PriorityQueue
{
    void Push(const T& x) // O(lgN)
    {
        _hp.Push(x);
    }

    void Pop() // O(lgN)
    {
        _hp.Pop();
    }

    T& Top()
    {
        return _hp.Top();
    }

protected:
    Heap<T, Compare> _hp;
};

2，堆排序（升序）
升序：建最大堆，然后最大的和最后一个结点进行交换，然后size–，然后在用次大的和size-1进行交换，直到只剩下最后一个数，停止交换。
如图：

代码如下：

//堆排序（升序）
void adjustDown(int* a,size_t n,int root)
{
    int parent = root;
    int child = parent * 2 + 1;
    while (child<n)
    {
        if (child + 1 < n&&a[child + 1] > a[child])
        {
            ++child;
        }
        if (a[child] > a[parent])
        {
            swap(a[child], a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }

    }
}

void HeapSort(int*a, size_t n)
{
    //建堆(升序建大堆)
    for (int i = (n - 2) / 2; i >= 0; --i)
    {
        adjustDown(a, n, i);
    }
    int end = n - 1;
    while (end >= 0)
    {
        swap(a[0], a[end]);
        adjustDown(a, end, 0);
        --end;
    }
}

3，在N个数中找出最大的前K个数
N个数找出最大的前K个
思想：如果我们N非常大的时候， 内存是放不下的
建立一个K大小的堆，如果建立最大堆，那么只能找到最大的一个，所以我们要建立小堆
方法：遍历N个数，先用前K个数建立一个小堆，下一个数如果比堆顶数据大的话，那么替代堆顶数据（因为堆顶数据是最小的），并且向下调整，最后堆里面的就是最大的前K个数，最大的前K个一定会进堆。
时间复杂度为N*lgK(严格来说为K*lgK+(N-K)*lgK，但是N一般远大于K，所以时间复杂度为N*lgK)。建立K个数的堆为的时间复杂度为N*lgN
代码实现如下

//向下调整（小堆）
void AdjustDown(int* a, size_t n, int root)
{
    assert(a);
    int parent = root;
    int child = parent * 2 + 1;
    while (child<n)
    {
        if (child + 1 < n&&a[child + 1] < a[child])
        {
            ++child;
        }
        if (a[child] < a[parent])
        {
            swap(a[child], a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }

    }


}
//N个数里面找最大的前K个
const size_t N = 10000;
const size_t K = 10;
void TopK()
{
    int a[N] = { 0 };
    for (size_t i = 0; i < N; ++i)
    {
        a[i] = rand() % N;//给随机数
    }
    //为了验证
    a[0] = N + 100;
    a[100] = N + 101;
    a[2] = N + 102;
    a[50] = N + 105;
    a[1000] = N + 100;
    a[1005] = N + 1550;
    a[888] = N + 130;
    a[9998] = N + 100;
    a[9999] = N + 100;
    a[9444] = N + 100;


    //堆就是一个数组
    int heap[K] = { 0 };
    //将前K个数放入堆中
    for (size_t i = 0; i < K; ++i)
    {
        heap[i] = a[i];
    }

    // 建堆
    for (int i = (K - 2) / 2; i >= 0; --i)
    {
        AdjustDown(heap, K, i);
    }

    for (size_t i = K; i < N; ++i)
    {
        if (a[i] > heap[0])
        {
            heap[0] = a[i];
            AdjustDown(heap, K, 0);
        }
    }

    for (size_t i = 0; i < K; ++i)
    {
        cout << heap[i] << " ";
    }

}

其中堆的应用最后两个（堆排序，找N个数中最大的前K个数）
我们可以通过调整AdjustDown（）函数可以实现堆排序的降序以及，找N个数中最小的前K个数，这里就不给大家举例子了。

最小堆和最大堆在代码上的区别主要是在向上调整和向下调整的区别上（只是三个符号上的区别，但是写两个函数代价大），我们要增强代码的复用性，我们可以用仿函数，以下的完整代码我们用仿函数来实现出来

模拟实现堆完整代码

#pragma once
#include<iostream>
#include<assert.h>
#include<vector>
using namespace std;

template<class T>
struct Less
{
    bool operator()(const T& left, const T& right) const
    {
        return left < right;
    }
};

template<class T>
struct Greater
{
    bool operator()(const T& left, const T& right) const
    {
        return left > right;
    }
};


template<class T,class Compare=Greater<T>>
class Heap
{
public:
    Heap()//无参的构造函数（系统不会给无参构造函数），开始堆是空的不需要做什么事
    {}
    Heap(T* a, size_t n)
    {
        _a.reserve(n);//开空间
        for (size_t i = 0; i < n; ++i)
        {
            _a.push_back(a[i]);

        }
        //建堆,找最后一个非叶子节点
        for (int i = (_a.size() - 2) / 2; i >= 0; --i)//不用size_t，因为i在这可能等于0，用size_t会死循环
        {
            AdjustDown(i);
        }
    }
    //向下调整
    void AdjustDown(int root)
    {
        Compare com;
        int parent = root;
        int child = parent * 2 + 1;//默认为左孩子
        while (child < _a.size())
        {
            //选出大孩子
            //if (child+1 < _a.size() && _a[child + 1] > _a[child])
            if (child+1 < _a.size() && com(_a[child + 1] , _a[child]))
            {
                ++child;
            }
            //如果孩子大于父亲则交换，否则跳出循环
            //if (_a[child] > _a[parent])
            if (com(_a[child],_a[parent]))
            {
                swap(_a[child], _a[parent]);//交换值
                parent = child;
                child = parent * 2 + 1;
            }
            else
            {
                break;
            }
        }
    }
    //向上调整
    void AdjustUp(int child)
    {
        Compare com;
        int parent = (child - 1) / 2;
        while (child > 0)
        {
            //if (_a[child] > _a[parent])
            if (com(_a[child] , _a[parent]))
            {
                swap(_a[parent], _a[child]);
                child = parent;
                parent = (child - 1) / 2;
            }
            else
            {
                break;
            }
        }

    }
    //最后插入
    void Push(const T&x)
    {
        _a.push_back(x);
        AdjustUp(_a.size() - 1);
    }
    //删除最大数
    void Pop()
    {
        assert(!_a.empty());
        swap(_a[0], _a[_a.size() - 1]);
        _a.pop_back();
        AdjustDown(0);

    }
    //取顶元素
    T& Top()
    {
        assert(!_a.empty());
        return _a[0];
    }
    size_t Size()
    {
        return _a.size();
    }

    bool Empty()
    {
        return _a.empty();
    }

    bool IsHeap()
    {
        //return _IsHeap(_root);//递归
        //非递归
        for (size_t i = 0; i <= (_a.size() - 2) / 2; i++)
        {
            int left = i * 2 + 1;
            int right = i * 2 + 2;
            //最后一个非叶子结点左孩子一定存在，但是右孩子不一定存在
            if (_a[i] < _a[left] || (right < _a.size() && _a[i] < _a[right]))
            {
                return false;
            }
            return true;
        }

    }
    bool _IsHeap(int root)
    {
        if (root >= _a.size())//不存在,是大堆
            return true;
        int left = root * 2 + 1;
        int right = root * 2 + 2;
        if (left < _a.size())
        {
            if (_a[left] > _a[root])
            {
                return false;
            }
            if (right < _a.size())
            {
                if (_a[right] > _a[root])
                {
                    return false;
                }
            }
        }
        return _IsHeap(left) && _IsHeap(right);

    }
private:
    vector<T> _a;

};

void Test() 
{ 
    int a[] = { 10, 11, 13, 12, 16, 18, 15, 17, 14, 19 };
    Heap<int> hp1(a, sizeof(a) / sizeof(a[0]));
    cout << "hp1" << hp1.IsHeap() << endl;
} 

////向下调整（大堆）
void AdjustDownBig(int* a, size_t n, int root)
{
    assert(a);
    int parent = root;
    int child = parent * 2 + 1;
    while (child<n)
    {
        if (child + 1 < n&&a[child + 1] > a[child])
        {
            ++child;
        }
        if (a[child] > a[parent])
        {
            swap(a[child], a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }

    }


}
//堆排序
void HeapSort(int*a, size_t n)
{
    //建堆(升序建大堆 O(N*lgN))
    for (int i = (n - 2) / 2; i >= 0; --i)
    {
        AdjustDownBig(a, n, i);
    }
    // 选择
    int end = n - 1;
    while (end >= 0)
    {
        swap(a[0], a[end]);
        AdjustDownBig(a, end, 0);
        --end;
    }
}
//向下调整（小堆）
void AdjustDownSmall(int* a, size_t n, int root)
{
    assert(a);
    int parent = root;
    int child = parent * 2 + 1;
    while (child<n)
    {
        if (child + 1 < n&&a[child + 1] < a[child])
        {
            ++child;
        }
        if (a[child] < a[parent])
        {
            swap(a[child], a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }

    }


}
//N个数里面找最大的前K个
const size_t N = 10000;
const size_t K = 10;
void TopK()
{
    int a[N] = { 0 };
    for (size_t i = 0; i < N; ++i)
    {
        a[i] = rand() % N;//给随机数
    }
    //验证
    a[0] = N + 100;
    a[100] = N + 101;
    a[2] = N + 102;
    a[50] = N + 105;
    a[1000] = N + 100;
    a[1005] = N + 1550;
    a[888] = N + 130;
    a[9998] = N + 100;
    a[9999] = N + 100;
    a[9444] = N + 100;


    //堆就是一个数组
    int heap[K] = { 0 };
    //将前K个数放入堆中
    for (size_t i = 0; i < K; ++i)
    {
        heap[i] = a[i];
    }

    // 建堆
    for (int i = (K - 2) / 2; i >= 0; --i)
    {
        AdjustDownSmall(heap, K, i);
    }

    for (size_t i = K; i < N; ++i)
    {
        if (a[i] > heap[0])
        {
            heap[0] = a[i];
            AdjustDownSmall(heap, K, 0);
        }
    }

    for (size_t i = 0; i < K; ++i)
    {
        cout << heap[i] << " ";
    }

}
void TestHeapSort()
{
    int a[] = { 10, 11, 13, 12, 16, 18, 15, 17, 14, 19 };
    HeapSort(a, sizeof(a) / sizeof(a[0]));
    for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}