priorityqueue实现说明

图标

豆瓜

豆瓜网

豆瓜网专栏

首发
豆瓜 图标 2020-09-10 19:25:46

优先队列严格说实际上不是一种队列,因为它并不需要遵循队列的FIFO特性,而要求的基本操作包括:向队列中插入新的记录,以及移出队列中的最大的元素。我们可以以各种不同的方式来实现优先队列——只要能够满足上面的两个接口就可以了。但是基于堆的优先队列则具有较好的性能。

优先队列是一种很有用的数据结构,因为实际上我们不是每时每刻都需要对数据进行严格的排序,有时候我们仅仅能够获得最大的元素的即可,但是如果以顺序查找的方式实现的话,效率上根本满足不了要求。而堆则提供了一种较高效率的实现策略。

      这里给出一个最小堆的实现,并且结合两个应用进行说明,一个是堆排序,一个是在n个数中寻找第k大的数。

template<typename T>
class CPriorityQueue
{//优先队列类
public:
    CPriorityQueue(int maxElements=0);
    CPriorityQueue(T *data,int n);
    ~CPriorityQueue(void);
    void Insert(const T& num);//插入优先队列
    T DeleteMin();//返回最小值
    bool isEmpty()const;//是否空队列
    bool isFull()const;//是否已经满了
private:
    int capicity;//容量
    int size;//当前大小
    T *elements;//元素存储区
    void init(int n);//初始化
    void destroy();//销毁优先队列
};

 

#include "stdafx.h"
#include <cstdlib>
#include "PriorityQueue.h"
#include <iostream>
using namespace std;

template<typename T>
void CPriorityQueue<T>::init(int n)
{//初始化
    this->elements = new T[n+1];
    this->capicity = n;
    this->size = 0;
}
template<typename T>
CPriorityQueue<T>::CPriorityQueue(int maxElements)
{
    this->init(maxElements);
}
template<typename T>
CPriorityQueue<T>::CPriorityQueue(T *data,int n)
{
    this->init(n);
    for(int i=0;i<n;++i)
    {
        this->Insert(data[i]);
    }
}
template<typename T>
void CPriorityQueue<T>::destroy()
{//销毁优先队列
    if(this->elements!=NULL)
    {
        delete[] elements;
        this->elements = NULL;
        this->size = 0;
    }
}
template<typename T>
CPriorityQueue<T>::~CPriorityQueue(void)
{
    this->destroy();
}
template<typename T>
bool CPriorityQueue<T>::isEmpty()const
{
    return this->size==0;
}
template<typename T>
bool CPriorityQueue<T>::isFull() const
{
    return this->size == this->capicity;
}
template<typename T>
void CPriorityQueue<T>::Insert(const T& num)
{//入队列
    if(!this->isFull())
    {
        int i;
        for(i = ++this->size;num<this->elements[i/2];i/=2)
            this->elements[i] = this->elements [i/2];
        this->elements[i] = num;
    }
}
template<typename T>
T CPriorityQueue<T>::DeleteMin()
{
    T minElement,lastElement;
    int i,child;
    if(!this->isEmpty())
    {
        minElement = this->elements[1];//最小的
        lastElement = this->elements[this->size--];//最后一个元素
        for(i=1;i*2<=this->size;i=child)
        {
            child = i*2;
            if(child!=this->size&&this->elements[child+1]<this->elements[child])
                child++;
            if(lastElement>this->elements[child])
            {
                this->elements[i] = this->elements[child];
            }
            else
                break;
        }
        this->elements[i] = lastElement;
        return minElement;
    }
    return this->elements[0];//失败
}

 

// Test.cpp : Defines the entry point for the console application.
//
/*
**author:phinecos
**date:7/19/2008
*/
#include "stdafx.h"
#include "PriorityQueue.cpp"
#include <iostream>
using namespace std;

void printArray(int *data,int n)
{
    int i;
    for(i=0;i<n;++i)
    {
        cout<<data[i]<<" ";
    }
    cout<<endl;
}
void HeapSort(int *data,int n)
{//堆排序
    CPriorityQueue<int> *pQueue = new CPriorityQueue<int>(data,n);
    int i;
    for(i=0;i<n;++i)
    {
        data[i] = pQueue->DeleteMin();
    }
    delete pQueue;
}
int FindKthMax(int *data,int n,int k)
{//在n个数中找第k大的数
    CPriorityQueue<int> *pQueue = new CPriorityQueue<int>(data,n);
    int i,result;
    for(i=0;i<k;++i)
    {
        result = pQueue->DeleteMin();
    }
    delete pQueue;
    return result;
}
int main(int argc, char* argv[])
{
    int a[] = {10,32,55,41,39,12,11,15,20,19,21,22,29,25};
    int len = sizeof(a)/sizeof(int);
    //堆排序演示
    cout<<"排序前: "<<endl;
    printArray(a,len);
    HeapSort(a,len);
    cout<<"排序后: "<<endl;
    printArray(a,len);
    //寻找第k大数演示
    cout<<"请输入k下标: "<<endl;
    int k;
    cin>>k;
    cout<<"第k大数是: "<<FindKthMax(a,len,k)<<endl;
    system("pause");
    return 0;
}


本文由豆瓜网专栏作家 豆瓜 投稿发布,并经过豆瓜网编辑审核。

转载此文章须经作者同意,并附上出处(豆瓜网)及本页链接。

若稿件文字、图片、视频等内容侵犯了您的权益,请联系本站进行 投诉处理

相关搜索

priorityqueue
图标 图标

豆瓜

豆瓜网

豆瓜网专栏

  • priorityqueue实现说明

    图标
    豆瓜 图标 · 今天 19:25:46 · 0浏览
  • lightswitch框架说明

    图标
    豆瓜 图标 · 今天 19:24:54 · 9浏览
  • 用户体验的五项原则

    图标
    豆瓜 图标 · 今天 19:23:43 · 6浏览
  • 全部评论

    豆瓜

    豆瓜网

    豆瓜网专栏

  • priorityqueue实现说明
  • lightswitch框架说明
  • 用户体验的五项原则
  • 网页设计规范尺寸
  • objective c入门说明
  • 我来说两句