数据结构 之 堆（完全二叉树、大根堆、小根堆）

堆是一种完全二叉树结构，这意味着它具有完全二叉树的性质，其中一点如下所示：

设完全二叉树的一元素编号为i，1 <= I <= n，n为元素总数。有以下关系成立：
1、如果i=1，则该元素为二叉树的根节点，若i>1，则其父节点的编号为(int)(i/2)；
2、如果2*i > n，则该元素无左孩子。否则，其左孩子的编号为2 * i;
3、如果1 + 2*i > n ，则该元素无右孩子，否则，其右孩子的编号为1+2*i

之前在看堆结构的内容的时候，误认为需要将树结构引入进来进行堆中元素的管理。但是因为上面的性质使得这一切不在需要树结构。使用数组的方式就能够管理。
大根堆是大根树的一种。大根树是一种父节点值始终大于其子节点的值的结构。根树不是完全二叉树类型的，但是根堆是。
下面以大根堆为例，进行对这种具有一定属性的堆结构的插入、删除、构造和“整理”操作：
插入节点
在插入的时候，首先将数据放置到完全二叉树的下一个子节点上。然后判断其与父节点值得大小，如果父节点的值小，那么将父节点和子节点的值进行交换；交换完成之后，接着判断插入数值所在的节点与其父节点的值大小，如果仍旧是父节点的数值小，则继续交换……直到满足父节点的数值更大或者不存在父节点的情况发生。
以上面的示意图为例，如果我插入的是数值2。那么他本来就满足父节点大的情况，不需要进行任何操作。但是如果插入的是10，则需要将数值8 和数值6都向下降一级，同时，数值10一路升级到最顶点。

插入的代码如下所示：

//// 需要在堆底部增加一个元素，然后自底向上进行大小关系的比较和交换位置
    template<class T>
    void myHeapArray<T>::push_back(T val)
    {
        if (0 == (m_back - m_front + 1 + m_len) % m_len)////将要满了，扩容
        {
            T* p = new T[(int)(m_len * 1.2 + 1)];
            if (m_back >= m_front)/////正常模式，正常扩容，仅修改m_len即可
            {
                memcpy(p, m_ptr, sizeof(T) * m_len);
            }
            else////按照堆的安排方式，是不存在这种情况的，因为数组前面的位置不存在空出来的机会
            {
                memcpy(p, &(m_ptr[m_front]), sizeof(T) * (m_len - m_front));
                memcpy(&(p[m_len - m_front]), m_ptr, m_back);
                m_front = 0;
                m_back = (m_back - m_front) % m_len;
            }
            delete[] m_ptr;
            m_ptr = p;
            m_len = (int)(m_len * 1.2 + 1);
        }
        m_ptr[m_back] = val;
        m_back = m_back + 1;

        int curNode = m_back - 1;
        int parNode = (int)((m_front - 1 + curNode) / 2);
        while (parNode >= m_front)////还没有到达堆顶部
        {
            if (m_ptr[curNode] > m_ptr[parNode])////子节点的值比父节点的值大，需要交换
            {
                T tmp = m_ptr[curNode];
                m_ptr[curNode] = m_ptr[parNode];
                m_ptr[parNode] = tmp;

                curNode = parNode;
                parNode = (int)((m_front - 1 + curNode) / 2);
            }
            else////// 因为push的操作是在前面都遵循了一定的规范的，所以可以直接跳过
            {
                break;
            }
        }
    }

删除操作
删除操作的做法有点奇妙。因为删除操作是删除最上面的顶点，在删除之后，树会被分割成两棵树（如果存在两棵子树），不在便于维护，所以改为将最后的一个子节点移除出去，同时将其数值移动到顶点上面，这样保持了树的结构，还删除了一个顶点。但是，可以预见的是，现在这棵树已经不再满足是大根树的条件。需要对树进行“整理”。方法是从顶点开始，比较节点与子树（存在的话）的值大小，如果子树的数值大，那么就交换两个节点的数值，如果换下去之后的节点的数值仍旧比其子节点的数值小，则继续进行该操作知道满足父节点的数值大于子节点的数值，或者不存在子节点为止。

下面贴上从栈顶删除一个元素的代码

    ////从栈顶上删除一个元素
    //// 需要把堆底的元素挪到堆顶部，然后进行整理
    template<class T>
    T myHeapArray<T>::pop_front(void)
    {
        if(m_back == m_front)
        {
            throw("NoElmentToPop");
        }
        else
        {
            T val = m_ptr[m_front];
            ///// 其实没有必要取余数，利用数组进行堆管理不存在back到前面去的情况
            m_back = (m_len + m_back - 1) % m_len;///// 其实没有必要取余数，利用数组进行堆管理不存在back到前面去的情况
            ///// 把最后一个元素防止到最前面，覆盖掉，表示删除了顶部的元素
            m_ptr[m_front] = m_ptr[m_back];
            int curNode = m_front;
            int childNodeL = 2 * curNode - m_front + 1;
            int childNodeR = childNodeL + 1;
            int swapNode;
            int tmp;
            while (childNodeL < m_back)//////至少存在一个节点
            {
                if (childNodeR < m_back)/// 存在两个子节点
                {
                    ////// 至少存在一个子节点是大于父节点的，必然要进行交换
                    if (m_ptr[childNodeL] > m_ptr[curNode] || m_ptr[childNodeR] > m_ptr[curNode])
                    {
                        if (m_ptr[childNodeL] > m_ptr[childNodeR])
                        {
                            swapNode = childNodeL;
                        }
                        else
                        {
                            swapNode = childNodeR;
                        }
                    }
                    else//// 两个子节点都比父节点小，可以不继续交换了
                    {
                        break;
                    }
                }
                else////只存在一个左子节点
                {
                    if (m_ptr[curNode] < m_ptr[childNodeL])//// 子节点的数值比较大，需要进行交换
                    {
                        swapNode = childNodeL;
                    }
                    else//// 只有一个节点，而且节点大小也满足停止条件
                    {
                        break;
                    }
                }
                tmp = m_ptr[swapNode];
                m_ptr[swapNode] = m_ptr[curNode];
                m_ptr[curNode] = tmp;

                //// 更新位置
                curNode = swapNode;
                childNodeL = 2 * curNode - m_front + 1;
                childNodeR = childNodeL + 1;
            }
            return(val);
        }
    }

整理操作
整理操作是对一个没有大小关系的堆结构进行大小的定位，使堆结构能够具有大根或者小根的特点的操作。
下面的示意图是使用到的一些求节点的表达式：

下面是整理部分的代码，其实可以从整理的代码中可以看到，堆（也是完全二叉树，虽然在这里使用的是数组的管理方法，但是仍旧能够体现出树的递归的性质）。这部分的思考感觉在一些边缘条件上面还可以推敲，希望大家能留言多多指导

template<class T>
void myHeapArray<T>::sort(int pos)
{
    int curNode = pos;
    int childNodeL = 2 * curNode - m_front + 1;
    int childNodeR = childNodeL + 1;

    ////// 再次体现树结构的递归特点，虽然这里不是以树的的组织形式，而是数组的形式
    if (childNodeL < m_back)
    {
        sort(childNodeL);
    }
    if (childNodeR < m_back)
    {
        sort(childNodeR);
    }

    int swapNode;
    int tmp;
    while (childNodeL < m_back)//////至少存在一个节点
    {
        if (childNodeR < m_back)/// 存在两个子节点
        {
            ////// 至少存在一个子节点是大于父节点的，必然要进行交换
            if (m_ptr[childNodeL] > m_ptr[curNode] || m_ptr[childNodeR] > m_ptr[curNode])
            {
                if (m_ptr[childNodeL] > m_ptr[childNodeR])
                {
                    swapNode = childNodeL;
                }
                else
                {
                    swapNode = childNodeR;
                }
            }
            else//// 两个子节点都比父节点小，可以不继续交换了
            {
                break;
            }
        }
        else////只存在一个左子节点
        {
            if (m_ptr[curNode] < m_ptr[childNodeL])//// 子节点的数值比较大，需要进行交换
            {
                swapNode = childNodeL;
            }
            else//// 只有一个节点，而且节点大小也满足停止条件
            {
                break;
            }
        }
        tmp = m_ptr[swapNode];
        m_ptr[swapNode] = m_ptr[curNode];
        m_ptr[curNode] = tmp;

        //// 更新位置
        curNode = swapNode;
        childNodeL = 2 * curNode - m_front + 1;
        childNodeR = childNodeL + 1;
    }
}

构造操作
在写完上面的插入操作的时候，构造的操作也就变得简单了。既可以通过对数组逐个执行插入的操作来完成由数组到堆结构的构造，也可以由整理操作来完成堆结构的大小定位。
下面贴上构造中使用的sort函数代码（对一棵树进行整理，使其符合大根堆或小根堆的特点）

    template<class T>
    void myHeapArray<T>::sort(int pos)
    {
        int curNode = pos;
        int childNodeL = 2 * curNode - m_front + 1;
        int childNodeR = childNodeL + 1;

        ////// 再次体现树结构的递归特点，虽然这里不是以树的的组织形式，而是数组的形式
        if (childNodeL < m_back)
        {
            sort(childNodeL);
        }
        if (childNodeR < m_back)
        {
            sort(childNodeR);
        }

        int swapNode;
        int tmp;
        while (childNodeL < m_back)//////至少存在一个节点
        {
            if (childNodeR < m_back)/// 存在两个子节点
            {
                ////// 至少存在一个子节点是大于父节点的，必然要进行交换
                if (m_ptr[childNodeL] > m_ptr[curNode] || m_ptr[childNodeR] > m_ptr[curNode])
                {
                    if (m_ptr[childNodeL] > m_ptr[childNodeR])
                    {
                        swapNode = childNodeL;
                    }
                    else
                    {
                        swapNode = childNodeR;
                    }
                }
                else//// 两个子节点都比父节点小，可以不继续交换了
                {
                    break;
                }
            }
            else////只存在一个左子节点
            {
                if (m_ptr[curNode] < m_ptr[childNodeL])//// 子节点的数值比较大，需要进行交换
                {
                    swapNode = childNodeL;
                }
                else//// 只有一个节点，而且节点大小也满足停止条件
                {
                    break;
                }
            }
            tmp = m_ptr[swapNode];
            m_ptr[swapNode] = m_ptr[curNode];
            m_ptr[curNode] = tmp;

            //// 更新位置
            curNode = swapNode;
            childNodeL = 2 * curNode - m_front + 1;
            childNodeR = childNodeL + 1;
        }
    }

下图是使用构造方式获得的大根堆：

下面贴上完整的堆结构的模板类代码，以及完整的贴图

    #ifndef _H_MYHEAPARRAY_H
    #define _H_MYHEAPARRAY_H
    #include <iostream>

    template<class T>
    class myHeapArray;

    template<class T>
    class myHeapArray
    {
    public:
        myHeapArray(int len = 64);
        myHeapArray(const myHeapArray<T>& mqa);
        myHeapArray(T arr[], int len);
        ~myHeapArray();

        T pop_front(void);
        void push_back(T val);
        int size(void);
        bool full(void);
        bool empty(void);
        T top();
        myHeapArray<T>& operator=(myHeapArray<T>& mqa);
        void printAll(void);
    private:
        void sort(int pos);
    private:
        T* m_ptr;
        int m_front;
        int m_back;
        int m_len;
    };

    //////////////// D E F I N I T I O N S /////////////////////////

    template<class T>
    myHeapArray<T>::myHeapArray(int len = 64)
    {
        std::cout<<"Constructor by Length"<<std::endl;
        m_front = 0;
        m_back = 0;
        if (len <= 0)
        {
            len = 16;
        }
        m_len = len;
        m_ptr = new T[m_len];
    }

    template<class T>
    myHeapArray<T>::myHeapArray(const myHeapArray<T>& mqa)
    {
        std::cout<<"Copy Constructor"<<std::endl;
        m_front = mqa.m_front;
        m_back = mqa.m_back;
        m_len = mqa.m_len;
        m_ptr = new T[m_len];
        memcpy(m_ptr, mqa.m_ptr, sizeof(T) * m_len);
        sort(m_front);
    }

    //template<class T>
    //myHeapArray<T>::myHeapArray(T arr[], int len)
    //{
    //  std::cout<<"Constructor by array"<<std::endl;
    //  m_front = 0;
    //  m_back = len;
    //  m_len = (int)(len * 1.2 + 1);
    //  m_ptr = new T[m_len];
    //  memcpy(m_ptr, arr, sizeof(T) * len);
    //  sort(m_front);
    //}

    /////////////////// 上面和下面的构造函数都可以，结果都符合大根堆的特点

    template<class T>
    myHeapArray<T>::myHeapArray(T arr[], int len)
    {
        std::cout<<"Constructor by array"<<std::endl;
        m_front = 0;
        m_back = 0;
        m_len = (int)(len * 1.2 + 1);
        m_ptr = new T[m_len];
        for (int ii = 0; ii < len; ii++)
        {
            push_back(arr[ii]);
        }
    }

    template<class T>
    myHeapArray<T>::~myHeapArray()
    {
        std::cout<<"Destructor"<<std::endl;
        if (NULL != m_ptr)
        {
            delete[] m_ptr;
        }
    }

    ////从栈顶上删除一个元素
    //// 需要把堆底的元素挪到堆顶部，然后进行整理
    template<class T>
    T myHeapArray<T>::pop_front(void)
    {
        if(m_back == m_front)
        {
            throw("NoElmentToPop");
        }
        else
        {
            T val = m_ptr[m_front];
            ///// 其实没有必要取余数，利用数组进行堆管理不存在back到前面去的情况
            m_back = (m_len + m_back - 1) % m_len;///// 其实没有必要取余数，利用数组进行堆管理不存在back到前面去的情况
            ///// 把最后一个元素防止到最前面，覆盖掉，表示删除了顶部的元素
            m_ptr[m_front] = m_ptr[m_back];
            int curNode = m_front;
            int childNodeL = 2 * curNode - m_front + 1;
            int childNodeR = childNodeL + 1;
            int swapNode;
            int tmp;
            while (childNodeL < m_back)//////至少存在一个节点
            {
                if (childNodeR < m_back)/// 存在两个子节点
                {
                    ////// 至少存在一个子节点是大于父节点的，必然要进行交换
                    if (m_ptr[childNodeL] > m_ptr[curNode] || m_ptr[childNodeR] > m_ptr[curNode])
                    {
                        if (m_ptr[childNodeL] > m_ptr[childNodeR])
                        {
                            swapNode = childNodeL;
                        }
                        else
                        {
                            swapNode = childNodeR;
                        }
                    }
                    else//// 两个子节点都比父节点小，可以不继续交换了
                    {
                        break;
                    }
                }
                else////只存在一个左子节点
                {
                    if (m_ptr[curNode] < m_ptr[childNodeL])//// 子节点的数值比较大，需要进行交换
                    {
                        swapNode = childNodeL;
                    }
                    else//// 只有一个节点，而且节点大小也满足停止条件
                    {
                        break;
                    }
                }
                tmp = m_ptr[swapNode];
                m_ptr[swapNode] = m_ptr[curNode];
                m_ptr[curNode] = tmp;

                //// 更新位置
                curNode = swapNode;
                childNodeL = 2 * curNode - m_front + 1;
                childNodeR = childNodeL + 1;
            }
            return(val);
        }
    }

    template<class T>
    void myHeapArray<T>::sort(int pos)
    {
        int curNode = pos;
        int childNodeL = 2 * curNode - m_front + 1;
        int childNodeR = childNodeL + 1;

        ////// 再次体现树结构的递归特点，虽然这里不是以树的的组织形式，而是数组的形式
        if (childNodeL < m_back)
        {
            sort(childNodeL);
        }
        if (childNodeR < m_back)
        {
            sort(childNodeR);
        }

        int swapNode;
        int tmp;
        while (childNodeL < m_back)//////至少存在一个节点
        {
            if (childNodeR < m_back)/// 存在两个子节点
            {
                ////// 至少存在一个子节点是大于父节点的，必然要进行交换
                if (m_ptr[childNodeL] > m_ptr[curNode] || m_ptr[childNodeR] > m_ptr[curNode])
                {
                    if (m_ptr[childNodeL] > m_ptr[childNodeR])
                    {
                        swapNode = childNodeL;
                    }
                    else
                    {
                        swapNode = childNodeR;
                    }
                }
                else//// 两个子节点都比父节点小，可以不继续交换了
                {
                    break;
                }
            }
            else////只存在一个左子节点
            {
                if (m_ptr[curNode] < m_ptr[childNodeL])//// 子节点的数值比较大，需要进行交换
                {
                    swapNode = childNodeL;
                }
                else//// 只有一个节点，而且节点大小也满足停止条件
                {
                    break;
                }
            }
            tmp = m_ptr[swapNode];
            m_ptr[swapNode] = m_ptr[curNode];
            m_ptr[curNode] = tmp;

            //// 更新位置
            curNode = swapNode;
            childNodeL = 2 * curNode - m_front + 1;
            childNodeR = childNodeL + 1;
        }
    }

    //// 需要在堆底部增加一个元素，然后自底向上进行大小关系的比较和交换位置
    template<class T>
    void myHeapArray<T>::push_back(T val)
    {
        if (0 == (m_back - m_front + 1 + m_len) % m_len)////将要满了，扩容
        {
            T* p = new T[(int)(m_len * 1.2 + 1)];
            if (m_back >= m_front)/////正常模式，正常扩容，仅修改m_len即可
            {
                memcpy(p, m_ptr, sizeof(T) * m_len);
            }
            else////按照堆的安排方式，是不存在这种情况的，因为数组前面的位置不存在空出来的机会
            {
                memcpy(p, &(m_ptr[m_front]), sizeof(T) * (m_len - m_front));
                memcpy(&(p[m_len - m_front]), m_ptr, m_back);
                m_front = 0;
                m_back = (m_back - m_front) % m_len;
            }
            delete[] m_ptr;
            m_ptr = p;
            m_len = (int)(m_len * 1.2 + 1);
        }
        m_ptr[m_back] = val;
        m_back = m_back + 1;

        int curNode = m_back - 1;
        int parNode = (int)((m_front - 1 + curNode) / 2);
        while (parNode >= m_front)////还没有到达堆顶部
        {
            if (m_ptr[curNode] > m_ptr[parNode])////子节点的值比父节点的值大，需要交换
            {
                T tmp = m_ptr[curNode];
                m_ptr[curNode] = m_ptr[parNode];
                m_ptr[parNode] = tmp;

                curNode = parNode;
                parNode = (int)((m_front - 1 + curNode) / 2);
            }
            else////// 因为push的操作是在前面都遵循了一定的规范的，所以可以直接跳过
            {
                break;
            }
        }
    }

    template<class T>
    int myHeapArray<T>::size(void)
    {
        return((m_back - m_front + 1 + m_len) % m_len);
    }

    template<class T>
    bool myHeapArray<T>::full(void)
    {
        return(0 == (m_back - m_front + 1 + m_len) % m_len);
    }

    template<class T>
    bool myHeapArray<T>::empty(void)
    {
        return(m_back == m_front);
    }

    template<class T>
    T myHeapArray<T>::top()
    {
        if (m_front != m_back)
        {
            return(m_ptr[m_front]);
        }
        else
        {
            throw("NoElement");
        }
    }

    template<class T>
    myHeapArray<T>& myHeapArray<T>::operator=(myHeapArray<T>& mqa)
    {
        std::cout<<"OverLoad Operator"<<std::endl;
        if (this != &mqa)
        {
            m_len = mqa.m_len;
            m_front = mqa.m_front;
            m_back = mqa.m_back;
            delete[] m_ptr;
            m_ptr = new T[m_len];
            memcpy(m_ptr, mqa.m_ptr, sizeof(T) * m_len);
            sort(m_front);
        }
        return(*this);
    }

    template<class T>
    void myHeapArray<T>::printAll(void)
    {
        std::cout<<std::endl;
        for (int ii = m_front; ii < m_back; ii++)
        {
            std::cout<<"\t"<<m_ptr[ii];
        }
        std::cout<<std::endl;
    }
    #endif

下图是思考过程中使用的一张插图：