数据结构与算法——优先队列类的C++实现(二叉堆)

优先队列简介：

操作表明上看着是支持多个应用程序同时运行，事实上是每个时刻只能有一个进程运行，操作系统会调度不同的进程去运行。每个进程都只能运行一个固定的时间，当超过了该时间，操作系统就会暂停当前运行的进程，去调度其它进程来执行。

实现这种进程调度的一种方法是使用队列。开始的时候进程被放在队列的末尾，调度程序将反复提取队列中的第一个进程来执行，直到运行完毕或时间片用完，若进程没有运行完毕则将该进程放入队列的末尾。这种策略不是特别合适，因为可能一些短的进程需要等待很长的时间才能轮流到。一般来说，运行时间短的进程需要尽快的结束。所以那些运行时间短的进程需要比较高的优先权，同样，那些比较重要的进程也需要比较高的优先权。
这种特殊的应用需要一种特殊的队列-----优先队列。可以用二叉堆实现优先队列。

二叉堆简介：

二叉堆与二叉查找树类似，二叉树有两个性质：结构性质和堆序性质。

 

结构性质：

二叉堆是一棵完全二叉树，除了子节点外的其它节点都有两个儿子节点。
一棵高为h的完全二叉树有2^h到2^(h+1) - 1个节点。完全二叉树的高为log(n)，n为节点数目。
由于完全二叉树的特点，实现起来很简单，用简单的数组就可以实现。对于数组中的任意位置i上的元素，其左儿子在位置2*i上，右儿子在(2*i)+1上，其父节点在i/2上（让根节点在位置1）；

 

下面是一棵完全二叉树的数组实现图示：

 

 

堆序性质：

因为如果想快速找到最小单元，则最小单元应该在根上。在堆中，对于每一个节点x,x的值大于等于子节点（叶子节点除外）；没有二叉查找树的要求严格。

 

 

二叉堆的数据结构实现：

用一个数组 vector v;来存储所有的元素。
用currentsize来记录当前元素的数目。

 

 

vector array;//存储二叉堆的节点 
int currentsize;//当前二叉堆中的节点数目

 

二叉堆的主要成员函数：

bool isempty() const;//判断二叉堆是否为空
const comparable & findmin() const;//查找最小元素

void insert(const comparable & x);//插入元素x
void deletemin();//删除最小元素
void deletemin(comparable & minitem);//删除最小元素，并以引用的方式返回该最小元素
void makeempty();//清空该二叉堆 
void print() const;//打印该堆元素

void buildheap();//将元素移动到合适的位置
void percolatedown(int hole);//下移动

二叉堆的主要成员函数介绍：

 

 

1、插入insert()：

比如：当插入14的时候，第一步在堆的下一个可用的位置建立空穴，如果在该空穴插入14后满足堆序性，则插入成功。
但当在该空穴插入14之后不满足堆序性，则将该空穴的父节点移入空穴，之前的父节点的位置变为了空穴。
然后再尝试插入该新的空穴，如果不满足堆序，则重复之前的操作。

 

 

 

/****************************************************************
*   函数名称：insert(const comparable & x)
*   功能描述: 删除最小元素
*   参数列表: 无
*   返回结果：void 
*****************************************************************/
template
void binaryheap::insert(const comparable & x)
{
    if(currentsize == array.size()-1)
        array.resize(2 * array.size());//扩大堆中数组的容量

    //获得空穴的位置
    int hole = ++currentsize;

    //上滤
    for(; hole > 1 && x < array[hole/2]; hole /= 2)
        array[hole] = array[hole/2];
    //将x插入到合适的位置
    array[hole] = x;
}

 

2、删除最小元素deletemin()：

将堆中最小的一个元素删除之后（最下的元素位于堆数组的最前面），必须将堆中最后一个元素x移动到堆中的某个合适的位置。.

 

比如:在下图中删除最小元素的操作。
删除最小元素13，将最后一个元素31移动到13的位置；31比13的两个孩子的值都大，所有将两个孩子值比较小的上移动。所以将14上移动。然后31再和14的两个孩子的值比较，直到31比空穴的两个孩子的值都小，或者是空穴到了叶子节点，则直接将31插入到空穴。

 

 

/****************************************************************
*   函数名称：deletemin()
*   功能描述: 删除最小元素
*   参数列表: 无
*   返回结果：void 
*****************************************************************/
template
void binaryheap::deletemin()
{
    if(isempty()){
        cout << "binaryheap is empty." << endl;
        return;
    }

    array[1] = array[currentsize];//将最后一个元素移动到最小元素的位置
    currentsize--;//元素总数减去1
    //将最后一个元素移动到合适的位置
    percolatedown(1); 
}

/****************************************************************
*   函数名称：percolatedown(int hole)
*   功能描述: 将array(hole)处的值向下移动 
*   参数列表: hole为堆中元素的位置标号
*   返回结果：void 
*****************************************************************/
template
void binaryheap::percolatedown(int hole)
{
    int child;
    //先保存array[hole]的值
    comparable temp = array[hole];

    for(; hole * 2 <= currentsize; hole = child){
        child = hole * 2;

        //child != currentsize,表明此时空穴有右儿子
        //array[child] > array[child+1] 表明此时空穴有右儿子小于左儿子
        if(child != currentsize && array[child] > array[child+1])
            child++;//此时child表示为空穴的右儿子

        //空穴的右儿子小于array[hole]
        if(array[child] < temp)
            array[hole] = array[child];
        else
            break;
    }

    array[hole] = temp;
}

 

 

下面是main函数，主要是对散列表类进行测试。

 

//测试主函数
int main()
{
    srand(unsigned(time(0)));
    binaryheap binaryheap;

    vector v;

    for(int i = 0; i < 10; ++i)
        v.push_back(rand() % 10);
    cout << "v: ";
    for(int i = 0; i < 10; ++i)
        cout << v[i] << " ";
    cout << endl;
    

    for(int i = 0; i < 10; ++i)
        binaryheap.insert(v[i]);

    binaryheap.print();


    for(int i = 0; i < 12; i++){
        int minval = 0;
        binaryheap.deletemin(minval);
        cout << "删除最小元素："  << minval << endl;
        binaryheap.print();
    }

    cout << "*****************************************" << endl;
    cout << "测试第二个构造函数: " << endl;
    binaryheap binaryheap2(v);
    binaryheap2.print();

    for(int i = 0; i < 12; i++){
        int minval = 0;
        binaryheap2.deletemin(minval);
        cout << "删除最小元素："  << minval << endl;
        binaryheap2.print();
    }


    return 0;
}

下面是二叉堆类的源代码：

/*************************************************************************
	> file name: binaryheap.cpp
	> author: 
	> mail: 
	> created time: 2016年04月14日 星期四 11时37分43秒
 ************************************************************************/

#include 
#include 
#include 
#include 
using namespace std;



/******************************************
*   类的名称：二叉堆
******************************************/

template
class binaryheap
{
    public:
        explicit binaryheap(int capacity = 100):array(capacity), currentsize(0){}
        explicit binaryheap(const vector & items);

        bool isempty() const;//判断二叉堆是否为空
        const comparable & findmin() const;//查找最小元素
        
        void insert(const comparable & x);//插入元素x
        void deletemin();//删除最小元素
        void deletemin(comparable & minitem);//删除最小元素，并以引用的方式返回该最小元素
        void makeempty();//清空该二叉堆 
        void print() const;//打印该堆元素

    private:
        vector array;//存储二叉堆的节点 
        int currentsize;//当前二叉堆中的节点数目
    private:
        void buildheap();//将元素移动到合适的位置
        void percolatedown(int hole);//下移动
};

/****************************************************************
*   函数名称：print() const
*   功能描述: 打印该堆元素 
*   参数列表: 无 
*   返回结果：无
*****************************************************************/
template
void binaryheap::print() const
{
    cout << "二叉堆的元素: " << endl;
    for(int i = 1; i <= currentsize; ++i)
        cout << array[i] << " ";
    cout << endl;
}

/****************************************************************
*   函数名称：binaryheap(const vector & items)
*   功能描述: 构造函数
*   参数列表: items 是构造二叉堆需要的数据
*   返回结果：无
*****************************************************************/
template
binaryheap::binaryheap(const vector & items):array(items.size()+10), currentsize(items.size())
{
    for(unsigned i = 0; i < items.size(); ++i)
        array[i+1] = items[i];

    buildheap();
}
/****************************************************************
*   函数名称：buildheap()
*   功能描述: 将元素移动到合适的位置，满足堆序
*   参数列表: 无
*   返回结果：void
*****************************************************************/
template
void binaryheap::buildheap()
{
    for(int i = currentsize / 2; i > 0; --i)
        percolatedown(i);
}

/****************************************************************
*   函数名称：findmin()
*   功能描述: 查找最小元素
*   参数列表: 无
*   返回结果：返回最小元素的引用
*****************************************************************/
template
const comparable & binaryheap::findmin() const
{
   return array[1]; 
}

/****************************************************************
*   函数名称：insert(const comparable & x)
*   功能描述: 删除最小元素
*   参数列表: 无
*   返回结果：void 
*****************************************************************/
template
void binaryheap::insert(const comparable & x)
{
    if(currentsize == array.size()-1)
        array.resize(2 * array.size());//扩大堆中数组的容量

    //获得空穴的位置
    int hole = ++currentsize;

    //上滤
    for(; hole > 1 && x < array[hole/2]; hole /= 2)
        array[hole] = array[hole/2];
    //将x插入到合适的位置
    array[hole] = x;
}

/****************************************************************
*   函数名称：deletemin()
*   功能描述: 删除最小元素
*   参数列表: 无
*   返回结果：void 
*****************************************************************/
template
void binaryheap::deletemin()
{
    if(isempty()){
        cout << "binaryheap is empty." << endl;
        return;
    }

    array[1] = array[currentsize];//将最后一个元素移动到最小元素的位置
    currentsize--;//元素总数减去1
    //将最后一个元素移动到合适的位置
    percolatedown(1); 
}

/****************************************************************
*   函数名称：percolatedown(int hole)
*   功能描述: 将array(hole)处的值向下移动 
*   参数列表: hole为堆中元素的位置标号
*   返回结果：void 
*****************************************************************/
template
void binaryheap::percolatedown(int hole)
{
    int child;
    //先保存array[hole]的值
    comparable temp = array[hole];

    for(; hole * 2 <= currentsize; hole = child){
        child = hole * 2;

        //child != currentsize,表明此时空穴有右儿子
        //array[child] > array[child+1] 表明此时空穴有右儿子小于左儿子
        if(child != currentsize && array[child] > array[child+1])
            child++;//此时child表示为空穴的右儿子

        //空穴的右儿子小于array[hole]
        if(array[child] < temp)
            array[hole] = array[child];
        else
            break;
    }

    array[hole] = temp;
}
/****************************************************************
*   函数名称：deletemin(comparable & minitem)
*   功能描述: 删除最小元素
*   参数列表: minitem 将最小元素赋值给引用minitem
*   返回结果：void 
*****************************************************************/
template
void binaryheap::deletemin(comparable & minitem)
{
    if(isempty()){
        cout << "binaryheap is empty." << endl;
        return;
    }

    minitem = array[1];

    array[1] = array[currentsize--];
    percolatedown(1);
}

/****************************************************************
*   函数名称：makeempty()
*   功能描述: 情况二叉堆
*   参数列表: 无
*   返回结果：void 
*****************************************************************/
template
void binaryheap::makeempty()
{
    currentsize = 0;
}

/****************************************************************
*   函数名称：isempty()
*   功能描述: 判断二叉堆是否为空
*   参数列表: 无
*   返回结果：如果为空，则返回true，否则返回false
*****************************************************************/
template
bool binaryheap::isempty() const
{
    return currentsize == 0;
}




//测试主函数
int main()
{
    srand(unsigned(time(0)));
    binaryheap binaryheap;

    vector v;

    for(int i = 0; i < 10; ++i)
        v.push_back(rand() % 10);
    cout << "v: ";
    for(int i = 0; i < 10; ++i)
        cout << v[i] << " ";
    cout << endl;
    

    for(int i = 0; i < 10; ++i)
        binaryheap.insert(v[i]);

    binaryheap.print();


    for(int i = 0; i < 12; i++){
        int minval = 0;
        binaryheap.deletemin(minval);
        cout << "删除最小元素："  << minval << endl;
        binaryheap.print();
    }

    cout << "*****************************************" << endl;
    cout << "测试第二个构造函数: " << endl;
    binaryheap binaryheap2(v);
    binaryheap2.print();

    for(int i = 0; i < 12; i++){
        int minval = 0;
        binaryheap2.deletemin(minval);
        cout << "删除最小元素："  << minval << endl;
        binaryheap2.print();
    }


    return 0;
}

下面是程序的运行结果：

v: 5 3 8 4 3 6 1 5 4 5 
二叉堆的元素: 
1 3 3 4 4 8 6 5 5 5 
删除最小元素：1
二叉堆的元素: 
3 4 3 5 4 8 6 5 5 
删除最小元素：3
二叉堆的元素: 
3 4 5 5 4 8 6 5 
删除最小元素：3
二叉堆的元素: 
4 4 5 5 5 8 6 
删除最小元素：4
二叉堆的元素: 
4 5 5 6 5 8 
删除最小元素：4
二叉堆的元素: 
5 5 5 6 8 
删除最小元素：5
二叉堆的元素: 
5 6 5 8 
删除最小元素：5
二叉堆的元素: 
5 6 8 
删除最小元素：5
二叉堆的元素: 
6 8 
删除最小元素：6
二叉堆的元素: 
8 
删除最小元素：8
二叉堆的元素: 

binaryheap is empty.
删除最小元素：0
二叉堆的元素: 

binaryheap is empty.
删除最小元素：0
二叉堆的元素: 

*****************************************
测试第二个构造函数: 
二叉堆的元素: 
1 3 5 4 3 6 8 5 4 5 
删除最小元素：1
二叉堆的元素: 
3 3 5 4 5 6 8 5 4 
删除最小元素：3
二叉堆的元素: 
3 4 5 4 5 6 8 5 
删除最小元素：3
二叉堆的元素: 
4 4 5 5 5 6 8 
删除最小元素：4
二叉堆的元素: 
4 5 5 8 5 6 
删除最小元素：4
二叉堆的元素: 
5 5 5 8 6 
删除最小元素：5
二叉堆的元素: 
5 6 5 8 
删除最小元素：5
二叉堆的元素: 
5 6 8 
删除最小元素：5
二叉堆的元素: 
6 8 
删除最小元素：6
二叉堆的元素: 
8 
删除最小元素：8
二叉堆的元素: 

binaryheap is empty.
删除最小元素：0
二叉堆的元素: 

binaryheap is empty.
删除最小元素：0
二叉堆的元素: