堆及topk问题

堆的本质

vector+向下调整算法/向上调整算法。
注意：这个二叉树为完全二叉树

向下调整算法：

已知条件：从一个节点开始向下调整，已知这个节点的左右子树已经是大堆或小堆。
所以需要从第一个不是叶子节点的节点开始调整，而这个节点正好是最后一个节点的父节点。
i = (_v.size() - 2)>>1; i即是最后一个不是叶子节点的节点。

以小堆为例：

1.以删除堆顶元素为例来说明向下调整算法：

2.以向堆中插入节点来说明堆的向上调整算法：

代码如下：

Heap.h

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

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

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

template<class T, class Compare = Greater<T> >
class Heap
{
public:
    Heap()
    {}

    Heap(const T* a, size_t n)
    {
       _v.reserve(n);//可以提高效率
       for (size_t i = 0; i < n; ++i)
       {
           _v.push_back(a[i]);
       }

       //建堆
       for (int i = ((int)_v.size() - 2) >> 1; i >= 0; --i)
       {
           AjustDown(i);
       }
    }

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

    void Pop()
    {
       //1。先将堆顶元素与堆的最后一个元素交换
       swap(_v[0], _v[_v.size() - 1]);
       //2.删除掉最后一个节点
       _v.pop_back();
       //3.向下调整
       AjustDown(0);
    }

protected:
    //向上调整算法
    void AdjustUp(int index)
    {
       int child = index;
       int parent = (child - 1) >> 1;
       while (child > 0)
       {
           if (Compare()(_v[parent],_v[child]))
           {
               break;
           }
           else
           {
               swap(_v[child], _v[parent]);
               child = parent;
               parent = (child - 1) >> 1;
           }
       }

    }

    //向下调整
    void AjustDown(int root)
    {
       int parent = root;
       int child = parent * 2 + 1;//默认是左孩子
       while (child < _v.size())
       {
           if (child + 1 < _v.size() && Compare()(_v[child + 1], _v[child]))
           {
               child++;//保证child是最大的孩子节点
           }
           if (Compare()(_v[child],_v[parent]))
           {
               swap(_v[child], _v[parent]);//交换父节点和孩子节点
               parent = child;
               child = parent * 2 + 1;
           }
           else//不用交换：说明已经是最大的堆了
           {
               break;
           }
       }
    }

private:
    vector<T> _v;
};

测试用例：

#include"Heap1.h"

void Test()
{
    int array[] = {53,17,78,9,45,65,87,23};
    Heap<int,Less<int> > h(array,sizeof(array)/sizeof(int));
    //h.Push(80);
    h.Pop();
}

int main()
{
    Test();
    return 0;
}

---

堆的应用：

1.实现优先级队列：

#pragma once
#include"Heap1.h"

template<class T>
class PriorityQueue
{
public:
    PriorityQueue()
    {}

    void Push(const T& data)
    {
       hp.Push(data);
    }

    void Pop()
    {
       hp.Pop();
    }

    bool Empty()
    {
       return hp.Empty();
    }

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

    size_t Size()
    {
       return hp.Size();
    }

private:
    Heap<T> hp;
};

测试代码：

#include"Heap1.h"
#include"PriorityQueue1.h"

void TestHeap()
{
    int array[] = {53,17,78,9,45,65,87,23};
    Heap<int,Greater<int> > h(array,sizeof(array)/sizeof(int));
    cout << h.IsMaxHeap() << endl;
    //h.Push(80);
    h.Pop();
    cout << h.IsMaxHeap() << endl;
}

void TestQueue()
{
    int array[] = { 53, 17, 78, 9, 45, 65, 87, 23 };
    size_t len = sizeof(array) / sizeof(int);
    PriorityQueue<int> p;
    for (size_t index = 0; index < len; ++index)
    {
       p.Push(array[index]);
    }

    cout << p.Top() << endl;
    p.Pop();
    cout << p.Top() << endl;
}

int main()
{
    //TestHeap();
    TestQueue();
    return 0;
}

2.topk问题（也是海量数据处理问题）：

问题：需要从十亿个数据中找出最大的前k个数。

分析思路：

思路：不能使用排序，因为使用排序的话，内存就必须可以容纳十亿个数据，但是这很明显不可能，所以不能使用排序。

我们可以先从十亿个数据中取出前k（假如为100）个数据，使用这k个数据来建一个小堆，那么堆顶就是这个堆中最小的数据，
然后我们就从十亿减k个数据中取出一个数据赖和堆顶数据来进行比较，如果比堆大，那么就拿这个数据来替换堆顶数据。
然后采用向下调整算法，使之堆顶又是这个堆中最小的数据。依次比较。。替换。。。调整。。。
最终，堆中的前k个数据就是十亿个数据中最大的k个数据。

这里应该可以想到：最大的前k个数据一定会进堆。–>因为每次都是比较堆顶的数据和从剩余的数据进行比较，
而这个堆顶数据又是这个堆中最小的数据。

注意：不能建大堆，如果建大堆，然后从剩余的十亿数据中取数据，拿取到的数据和堆顶数据进行比较，
如果这个数据大于堆顶的数据，那么就交换两者的数据。最终只能找出十亿数据中最大的一个数据。—->不符合。

代码如下：

void Topk()
{
    int arr[N];
    int res[k];
    for (size_t i = 0; i < N; ++i)
    {
       arr[i] = rand() % N;
    }

    //验证topk问题
    /*arr[999] = N + 10;
    arr[898] = N + 23;
    arr[766] = N + 46;
    arr[3] = N + 59;
    arr[310] = N + 29;
    arr[19] = N + 58;
    arr[20] = N + 40;
    arr[209] = N + 12;
    arr[58] = N + 60;
    arr[334] = N + 14;*/

    //1.建一个小堆
    Heap<int, Less<int> > hp;
    for (size_t index = 0; index < k; ++index)
    {
       res[index] = arr[index];
    }

    //向下调整
    for (int i = (k - 2) / 2; i >= 0; --i)
    {
       AdjustDown(res, k, i);
    }

    //找出k个最大的数据
    for (size_t j = k; j < N; ++j)
    {
       if (res[0] < arr[j])
       {
           res[0] = arr[j];
           AdjustDown(res, k, 0);
       }
    }

    for (int j = 0; j < k; ++j)
    {
       cout << res[j] << " ";
    }
    cout << endl;
}

3.堆排序问题

升序（需要建一个大堆）

将0号下标的数据和最后一个数据交换，堆中数据个数减1，然后再向下调整，使得0号下标的数据是最大值，然后继续和堆中最后一个数据交换，继续将堆中元素个数减一。

降序（需要建一个小堆）

同上，将0号下标的数据和堆中最后一个数据进行交换，然后将堆的元素个数减一，再向下调整堆中数据，使得堆中的0号下标的数据称为现在堆中最小的数据。

代码如下：

//向下调整算法
void AdjustDown(int* heap, int n, int root)
{
    assert(heap);

    int parent = root;
    int child = parent*2+1;

    while (child < n)
    {
        if (child+1<n && heap[child+1] > heap[child])
        {
            ++child;
        }

        if (heap[child] > heap[parent])
        {
            swap(heap[child], heap[parent]);
            parent = child;
            child = parent*2+1;
        }
        else
        {
            break;
        }
    }
}

//堆排序

void HeapSort(int* a, size_t n)
{
    assert(a);

    // 建堆：时间复杂度 O(N*lgN)
    //从最后一个非叶子节点处开始向下调整
    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;
    }
}