欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

优先队列的多种语言实现形式

程序员文章站 2022-07-14 14:24:52
...

优先队列的定义

priority queue是出队的时候永远让具有最高或者最低优先级的数据先出队,而入队不做要求。即:

  • 出队:最高(最低)优先级的元素
  • 入队:无特别要求

现实的典型实例是医院就诊优先救治病情最危急的病人,银行优先处理高级客户等等。

实现

c实现

c语言实现优先队列可以使用最小堆。要理解最小堆首先要知道什么是最小树。最小树是指每个节点的元素均不大于其子节点的元素,而当这个最小树是完全二叉树时,就变成了最小堆。

#include <stdio.h>
#include <stdlib.h>
typedef int Elem;
struct heap{
    Elem *data;
    int capacity;
    int size;
};

typedef struct heap* Heap;
Heap initHeap(int max){
    Heap h;
    h = (Heap)malloc(sizeof(struct heap));
    if(!h)   return NULL;
    h->data = (Elem*)malloc(sizeof(Elem)*(max+1));
    if(!h->data)     return NULL;
    h->capacity = max;
    h->size = 0;
    return h;
}
void printHeap(Heap h){
    for(int i=1;i<=h->size;i++)
        printf("%d ",h->data[i]);
    putchar('\n');
}
int isFull(const Heap h){
    return h->capacity==h->size;
}
int isEmpty(const Heap h){
    return h->size==0;
}
void percolateUp(int k,Heap h){
    Elem x=h->data[k];
    int i;
    for(i=k;i>1&&h->data[i]<h->data[i/2];i=i/2){
        h->data[i]=h->data[i/2];
    }
    h->data[i]=x;
}
void percolateDown(int k,Heap h){
    Elem x=h->data[k];
    int i,child;
    for(i=k;i*2<=h->size;i=child){
        child = i*2;
        if(child!=h->size&&h->data[child]>h->data[child+1]) child+=1;   // 有右儿子 && 左儿子>右儿子
        if(h->data[i]>h->data[child])   h->data[i]=h->data[child];
    }
    h->data[i]=x;
}
int insertHeap(Elem x,Heap h){
    if(isFull(h))   return 0;
    h->data[++h->size] = x;
    percolateUp(h->size,h);
    return 1;
}
int removeHeap(Elem* px,Heap h){
    if(isEmpty(h))  return 0;
    *px=h->data[1];
    h->data[1]=h->data[h->size--];
    percolateDown(1,h);
    return 1;
}
Heap buildHeap(Elem* a,int size,int max){
    Heap h=initHeap(max);   //初始化堆
    if(!h)  return NULL;    // init fail,return null pointer
    h->size=size;
    for(int i=1;i<=size;i++){   // read list
        h->data[i]=a[i-1];
    }
    printHeap(h);
    for(int i=size/2;i>0;i--)   // percolate down
        percolateDown(i,h);
    return h;
}
int main(){
    Elem a[6]={10,50,60,5,30,20};
    Heap h=buildHeap(a,6,50);   // 创建一个容量为50的堆,先存入6个元素
    printHeap(h);
//    Heap h;
//    h = initHeap(10);
//    insertHeap(20,h);
//    printHeap(h);
//    insertHeap(10,h);
//    insertHeap(5,h);
//    insertHeap(15,h);
//    insertHeap(30,h);
//    insertHeap(18,h);
//    printHeap(h);
//    Elem x;
//    removeHeap(&x,h);
//    printf("%d\n",x);
//    printHeap(h);
    return 0;
}

C++实现

C++首先需要包含头文件。
priority queue默认是大顶堆,如下:

#include <iostream>
#include <queue>
using namespace std;

int main(){
    priority_queue<int> q;
    //等价于 priority_queue<int,vector<int>,less<int>> q;
    // 这就是大顶堆实现,如果要实现a>b的操作,也就是小顶堆,less换做greater
    q.push(1);
    q.push(2);
    q.push(3);
    cout<<q.top()<<endl;
    q.pop();
    cout<<q.top()<<endl;
    return 0;
}

输出结果:

3
2

Process returned 0 (0x0)   execution time : 0.086 s
Press any key to continue.

如果想要小顶堆

#include <iostream>
#include <queue>
using namespace std;

int main(){
    priority_queue<int,vector<int>,greater<int>> q;
    q.push(1);
    q.push(2);
    q.push(3);
    cout<<q.top()<<endl;
    q.pop();
    cout<<q.top()<<endl;
    return 0;
}

输出结果:

1
2

Process returned 0 (0x0)   execution time : 0.085 s
Press any key to continue.

python实现

python实现首先要包含queue这个库,默认的priority queue是small heap。实例如下:

import queue
q = queue.PriorityQueue()   
# default small heap
q.put(11)
q.put(22)
q.put(33)
print(q.get())

如果想实现大顶堆,可以采用自己建立一个类,如下面的方式:

import queue

class Elem:
    def __init__(self,x):
        self.data = x
    def __lt__(self,other): 
    # lt means less than, also have le(less or equal), gt(greater than), ge(greater or equal)
        return self.data < other.data

q = queue.PriorityQueue()   
# default small heap

q.put(Elem(11))
q.put(Elem(22))
q.put(Elem(33))
print(q.get().data)

输出结果为:

PS D:\C++_QJX> & C:/Users/QinJX/AppData/Local/Programs/Python/Python37/python.exe d:/Python_QJX/py_20191022_1.py
11

如果想实现大顶堆,可以 将 self.data < other.data 改为 self.data > other.data。