项目名称：文件压缩

• 实现思路如下

1. 用vector创建堆，而且是小堆
2. 从堆顶拿元素作为huffmanTree的叶子节点构建HuffmaTree,生成huffmanm编码
3. 写配置文件（方便后续的解压缩）
4. 压缩文件，根据配置文件解压缩文件

数据结构：vector； 堆（push,pop,top等基本操作）； huffmanTree(哈夫曼编码）；
string；atoi,itoa；文件的读写，写入，读出等基本操作；位运算，仿函数和运算符重载等

环境：VS2013

上面简述了本项目的一些基本的信息，看着是不是有点乱啊，没关系，咱们从堆开始一步一步
剖析它。废话不多说，先从堆说起。

堆部分讲解：

堆数据结构是一种数组对象，它可以被视为一棵完全二叉树结构。

堆结构的二叉树存储是

最大堆：每个父节点的都大于孩子节点。

最小堆：每个父节点的都小于孩子节点。

如图所示：它既不是最大堆也不是最小堆，那么就要对他进行调整，调整如下：
调整方式：向上调整，所谓向上调整，就是从从第一个非叶子节点开始调整，让每一个节点都满足小堆

特殊情况：将原来的19改为12，调整后他就发生了如下的变化，

如图所示，结果存在问题，所以这种情况就需要以该节点为根节点，向下调整

实现代码：

#pragma once
#pragma warning(disable:4018)
#include <vector>
#include<iostream>
using namespace std;

//仿函数
template <class T>
struct Less
{
    //重载 < ,如果是string类型，自定义string，string需重载 < 
    bool operator()(const T& a, const T& b)const
    {
        return a < b;
    }
};

template <class T>
struct Greater
{
    //重载 >
    bool operator()(const T& a, const T& b)const
    {
        return a > b;
    }
};

template <class T,class compare = NodeCompress<T>>
class MinHeap
{
public:
    MinHeap()
        :_array(NULL)
    {}
    // 最小堆
    //向上调整
    MinHeap(const vector<T>& array)
    {
        for (size_t i = 0; i < array.size(); ++i)
        {
            _array.push_back(array[i]);
        }
        moveUp(_array);
    }

    //打印结果
    void Display()
    {
        for (size_t i = 0; i < _array.size(); ++i)
        {
            cout << _array[i] << " ";
        }
        cout << endl;
    }

    //push(x)后向上调整
    void Push(const T& x)
    {
        _array.push_back(x);
        moveUp(_array);
    }

    void Pop()
    {
        if (!_array.empty())
        {
            swap(_array[0], _array[_array.size() - 1]);
            _array.pop_back();
            moveDown(0);
        }
    }

    //接口，得到堆顶的值，即最小值
    T& Top()
    {
        if (_array[0])
        {
            return _array[0];
        }
    }

    size_t Size()
    {
        return _array.size();
    }

    ~MinHeap()
    {}
public:
    bool IsEmpty()const
    {
        if (_array.empty())
        {
            return true;
        }
    }

    //向上调整
    void moveUp(vector<T>& array)
    {
        int child = array.size() - 1;
        int parent = (child-1) / 2;
        while (child > 0)
        {
            //如果右孩子存在，且小于左孩子
            if (child + 1 < array.size() && (compare()(array[child+1] , array[child])))
            {
                ++child;
            }

            //较小的一个和根节点比较
            if (compare()(array[child] , array[parent]))
            {
                swap(array[parent], array[child]);
                moveDown(child);
            }
            --parent;
            child = parent*2 + 1;
        }
    }

    //向上调整后，必须要向下调整，树的高度大于二可能出现bug,所以此举是确保万无一失
    //原理与向上相似，方向相反
    void moveDown(int parent)
    {
        int child = (parent) * 2 + 1;
        while (child < _array.size())
        {
            if (child + 1 < _array.size() && compare()(_array[child + 1] , _array[child]))
            {
                ++child;
            }
            if (compare()(_array[child] , _array[parent]))
            {
                swap(_array[parent], _array[child]);
                parent = child;
                child = child * 2 + 1;
            }
            else
            {
                break;
            }
        }
    }
private:
    vector<T> _array;
};

//测试堆
void testheap()
{
    vector<int> arr = { 10, 16, 18, 12, 9, 13, 15, 17, 14, 11 };
    MinHeap<int,Less<int>> heap(arr);
    heap.Display();

    heap.Push(2);
    heap.Display();

    heap.Pop();
    heap.Display();
}