数据结构--二叉堆与堆排序

向右看齐 2022-08-21 08:43 314阅读 0赞

#  #

# 二叉堆的概念 #

二叉堆，BinaryHeap，是二叉树中的常见的一种结构。通常以最大堆和最小堆的形式呈现。最大堆指的是父节点大于等于孩子节点的value值，也就是说对于最大堆而言，根元素是二叉堆最大的元素。最小堆的概念是与最大堆的概念是相似的。下图是最大堆的示意图：  
![Center][]

# 二叉堆和排序之间的联系 #

二叉堆最显著的特征就是根元素是二叉树元素间最大的或者最小的。因此每次将二叉树最大或者最小的元素取出来，同时保证每次进行这样的操作后，剩下的元素依然可以保持二叉堆的性质，这样迭代这个过程，就可以完成排序的目的。

所以，进行堆排序的过程，首先就需要进行待排序元素的堆建立过程。这里以最大堆为例。

## 堆的建立过程 ##

在建立最大堆的过程中，每插入一个元素，就要对元素进行一个上浮的操作。上浮是指对每个即将插入最大堆的元素进行判断，判断与当前元素与其父元素的大小关系，保持父元素与孩子元素之间的大小关系，重复这个过程，直到从根元素开始，所有的父元素和孩子元素都和二叉堆的定义保持一致。具体实现过程如下：

首先是最大堆的ADT:

template<class T>
    class BinaryHeap
    {
    public:
        BinaryHeap(int capacity);
        ~BinaryHeap();
    
        void filterUp(int start);
        void Insert(T &data);
    
    
        T delHeap();
    
        void BuildHeap(vector<T> initArray);
        void displayHeap();
    
    private:
        T *m_pData;
        int mCurSize;
        int mCapacity;
    };

然后是最大堆的建立过程：

template<class T>
    void BinaryHeap<T>::filterUp(int start)
    {
    
        int nIndex=start;
        T temp=m_pData[nIndex];
        int parentIndex=(int) start/2;
    
        while(nIndex>0)
        {
            if(m_pData[parentIndex]<temp)
            {
                m_pData[nIndex]=m_pData[parentIndex];
                nIndex=parentIndex;
                parentIndex=(int) nIndex/2;
            }
            else
                break;
        }
        m_pData[nIndex]=temp;
    
    }
    
    template<class T>
    void BinaryHeap<T>::Insert(T &data)
    {
        if(mCurSize>=mCapacity)
        {
            mCapacity*=2;
            mCurSize++;
        }
        m_pData[mCurSize]=data;
        filterUp(mCurSize);
    }

完成了最大堆的建立，就可以进行最大元素的抽取了，将抽取的元素存起来，就可以进行迭代过程的排序了：

这里在抽取最大元素的抽取后，相应的元素个数就会减少一个，如果是把根元素的孩子结点移动到根元素的位置，然后从上往下进行这样的移动，这样不能很好的保持完全二叉树的性质。因此这里采取的小技巧是，将二叉树的最后一个元素移动到根元素的位置，这样仅仅只是交换value值，不需要频繁的移动元素的位置。以下是该过程的示意图：

第一步：

![20160424222617272][]

![20160424222632651][]

第二步：

![20160424222656975][]

![20160424222709433][]

这样就完成了最大元素的抽取过程了，然后下面是具体的实现过程：

template<class T>
    T BinaryHeap<T>::delHeap()
    {
        int parentIndex=0;
        T tempMax=m_pData[parentIndex];
        int nIndex=parentIndex*2+1;
    
        m_pData[parentIndex]=m_pData[mCurSize-1];
        T tempCur=m_pData[parentIndex];
        while((nIndex+1)<mCurSize)
        {
    
            if(tempCur>=m_pData[nIndex] && tempCur>=m_pData[nIndex+1])
            {
    
                break;
            }
            else
            {
                if(m_pData[nIndex]>m_pData[nIndex+1])
                    {
                        m_pData[parentIndex]=m_pData[nIndex];
                        parentIndex=nIndex;
                    }
                else
                    {
                         m_pData[parentIndex]=m_pData[nIndex+1];
                         parentIndex=nIndex+1;
                    }
    
                         nIndex=2*parentIndex+1;
            }
        }
        m_pData[parentIndex]=tempCur;
        if(mCurSize>1)
            mCurSize--;
        else
        {
            mCurSize--;
            cout<<"the heap size is zero!"<<endl;
        }
        return tempMax;
    
    }

以上就是关键的过程的代码，下面是完整过程的代码：

首先是二叉堆的头文件：

#ifndef BINARYHEAP_H_INCLUDED
    #define BINARYHEAP_H_INCLUDED
    
    #include<vector>
    #include<queue>
    #include<iostream>
    using namespace std;
    template<class T>
    class BinaryHeap
    {
    public:
        BinaryHeap(int capacity);
        ~BinaryHeap();
    
        void filterUp(int start);
        void Insert(T &data);
    
    
        T delHeap();
    
        void BuildHeap(vector<T> initArray);
        void displayHeap();
    
    private:
        T *m_pData;
        int mCurSize;
        int mCapacity;
    };
    
    
    template<class T>
    BinaryHeap<T>::BinaryHeap(int capacity)
    {
        mCurSize=0;
        mCapacity=capacity;
        m_pData=new T[capacity];
    }
    
    template<class T>
    BinaryHeap<T>::~BinaryHeap()
    {
        mCurSize=0;
        mCapacity=0;
        delete []m_pData;
    }
    
    template<class T>
    void BinaryHeap<T>::filterUp(int start)
    {
    
        int nIndex=start;
        T temp=m_pData[nIndex];
        int parentIndex=(int) start/2;
    
        while(nIndex>0)
        {
            if(m_pData[parentIndex]<temp)
            {
                m_pData[nIndex]=m_pData[parentIndex];
                nIndex=parentIndex;
                parentIndex=(int) nIndex/2;
            }
            else
                break;
        }
        m_pData[nIndex]=temp;
    
    }
    
    template<class T>
    void BinaryHeap<T>::Insert(T &data)
    {
        if(mCurSize>=mCapacity)
        {
            mCapacity*=2;
            mCurSize++;
        }
        m_pData[mCurSize]=data;
        filterUp(mCurSize);
    }
    
    template<class T>
    void BinaryHeap<T>::BuildHeap(vector<T> initArray)
    {
        int nSize=initArray.size();
        if(nSize==0)
            return;
        else
        {
            for(int i=0;i<nSize;i++)
            {
                Insert(initArray.at(i));
                if(mCurSize<mCapacity)
                    mCurSize++;
                else
                {
                    mCapacity*=2;
                    mCurSize++;
                }
            }
    
        }
    }
    
    template<class T>
    T BinaryHeap<T>::delHeap()
    {
        int parentIndex=0;
        T tempMax=m_pData[parentIndex];
        int nIndex=parentIndex*2+1;
    
        m_pData[parentIndex]=m_pData[mCurSize-1];
        T tempCur=m_pData[parentIndex];
        while((nIndex+1)<mCurSize)
        {
    
            if(tempCur>=m_pData[nIndex] && tempCur>=m_pData[nIndex+1])
            {
    
                break;
            }
            else
            {
                if(m_pData[nIndex]>m_pData[nIndex+1])
                    {
                        m_pData[parentIndex]=m_pData[nIndex];
                        parentIndex=nIndex;
                    }
                else
                    {
                         m_pData[parentIndex]=m_pData[nIndex+1];
                         parentIndex=nIndex+1;
                    }
    
                         nIndex=2*parentIndex+1;
            }
        }
        m_pData[parentIndex]=tempCur;
        if(mCurSize>1)
            mCurSize--;
        else
        {
            mCurSize--;
            cout<<"the heap size is zero!"<<endl;
        }
        return tempMax;
    
    }
    
    template<class T>
    void BinaryHeap<T>::displayHeap()
    {
        for(int i=0;i<mCurSize;i++)
        {
            cout<<m_pData[i]<<"---";
        }
        cout<<endl;
    }
    
    
    
    #endif // BINARYHEAP_H_INCLUDED

然后是主过程的调用，在主过程完成排序：

#include <iostream>
    #include<cstdlib>
    #include<ctime>
    #include"BinaryHeap.h"
    
    using namespace std;
    
    int main()
    {
        srand(unsigned(time(NULL)));
    
        vector<int> initArray;
        int data=rand()%100;
        int length=rand()%15;
        int cnt=0;
        while(cnt<length)
        {
            initArray.push_back(data);
            data=rand()%100;
            cnt++;
        }
    
        cout<<"待排序序列："<<endl;
        for(int i=0;i<length;i++)
            cout<<initArray.at(i)<<"---";
        cout<<endl;
    
        BinaryHeap<int> heap(30);
        heap.BuildHeap(initArray);
        cout<<"建立好的最大堆："<<endl;
        heap.displayHeap();
    
        int maxEle;
        vector<int> sortedArray;
        for(int i=0;i<initArray.size();i++)
        {
            maxEle=heap.delHeap();
            sortedArray.push_back(maxEle);
    
        }
    
        cout<<"排序完成的序列："<<endl;
        for(int i=0;i<sortedArray.size();i++)
        {
            cout<<sortedArray.at(i)<<"---";
        }
            cout<<endl;
        cout << "Hello world!" << endl;
        return 0;
    }

然后结果如下：

![20160424223713665][]

[Center]: /images/20220724/1794cb90989343ffae5213eca59868da.png
[20160424222617272]: /images/20220724/221f37d6f1e54016b876209bf17ecc3b.png
[20160424222632651]: /images/20220724/74966508314b40f5adf513e2ddf1b9dc.png
[20160424222656975]: /images/20220724/bf90f4a35af0472ea8a5071013fd1a1b.png
[20160424222709433]: /images/20220724/2232d118ed984fd7bc595cb4d1bc01a2.png
[20160424223713665]: /images/20220724/a7d0a86a4b04425b8994a521bbbe0b48.png