优先级队列的两种不同定义？

Question

我不明白，如果两个优先级队列的下列定义是正确的：

1.

- 上升优先级队列 - 元素插入任意，但删除后，最小的元素删除（假设数据是一个整数）。

- 降序优先队列 - 元素被任意插入，但删除后，最大的元素被删除（假设数据是一个整数）。

每个

实例：

5 15 10 -> after dequeue() -> 15 10 
15 5 10 -> after dequeue() -> 5 10 

2.

优先级队列的每一个元素都有优先，通过该删除完成。 可能有两种情况。首先，移除最高优先级的元素。其次，删除最低优先级的元素。

显然，这与第一个定义不同。如果我们将优先级6,3,12分配给号码15, 10, 5，那么在dequeue()操作后有两种情况。如果最低优先级的元素被删除，则队列为15,5 (10 is removed)。如果具有最高优先级的元素被删除，则队列为15,10 (5 is removed)。另外，如果一个队列的元素不是数字（例如字符串），那么第一个定义是无用的。

这是正确的吗？

问题：两个定义是否正确？在我看来，第一个只能用于数字，但即使如此，它也违反了第二个定义中的优先。有人能解释这一点吗？

下面是一种在C两个定义两个实现：

  //1. DEFINITION// 
#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
#include <stdbool.h> 
#define MAX 6 

int intArray[MAX]; 
int itemCount = 0; 

int peek(){ 
    return intArray[itemCount - 1]; 
} 

bool isEmpty(){ 
    return itemCount == 0; 
} 

bool isFull(){ 
    return itemCount == MAX; 
} 

int size(){ 
    return itemCount; 
} 

void insert(int data){ 
    int i = 0; 

    if(!isFull()){ 
     // if queue is empty, insert the data 
     if(itemCount == 0){ 
     intArray[itemCount++] = data; 
     }else{ 
     // start from the right end of the queue 

     for(i = itemCount - 1; i >= 0; i--){ 
      // if data is larger, shift existing item to right end 
      if(data > intArray[i]){ 
       intArray[i+1] = intArray[i]; 
      }else{ 
       break; 
      } 
     } 

     // insert the data 
     intArray[i+1] = data; 
     itemCount++; 
     } 
    } 
} 

int removeData(){ 
    return intArray[--itemCount]; 
} 

int main() { 

    insert(3); 
    insert(5); 
    insert(9); 
    insert(1); 
    insert(12); 

    int num = removeData(); 
    printf("Element removed: %d\n",num); 

    return 0; 
} 

      //2. DEFINITION// 

#include<stdio.h> 
#include<stdlib.h> 
#define SIZE 5   /* Size of Queue */ 
int f=0,r=-1;  /* Global declarations */ 
typedef struct PRQ 
{ 
    int ele; 
    int pr; 
}PriorityQ; 

PriorityQ PQ[SIZE]; 

PQinsert(int elem, int pre) 
{ 
    int i;  /* Function for Insert operation */ 
    if(Qfull()) printf("\n\n Overflow!!!!\n\n"); 
    else 
    { 
     i=r; 
     ++r; 
     while(PQ[i].pr >= pre && i >= 0) /* Find location for new elem */ 
     { 
      PQ[i+1]=PQ[i]; 
      i--; 
     } 
     PQ[i+1].ele=elem; 
     PQ[i+1].pr=pre; 
    } 
} 

PriorityQ PQdelete() 
{      /* Function for Delete operation */ 
    PriorityQ p; 
    if(Qempty()){ printf("\n\nUnderflow!!!!\n\n"); 
    p.ele=-1;p.pr=-1; 
    return(p); } 
    else 
    { 
     p=PQ[f]; 
     f=f+1; 
     return(p); 
    } 
} 
int Qfull() 
{      /* Function to Check Queue Full */ 
    if(r==SIZE-1) return 1; 
    return 0; 
} 

int Qempty() 
{     /* Function to Check Queue Empty */ 
    if(f > r) return 1; 
    return 0; 
} 

display() 
{     /* Function to display status of Queue */ 
    int i; 
    if(Qempty()) printf(" \n Empty Queue\n"); 
    else 
    { 
     printf("Front->"); 
     for(i=f;i<=r;i++) 
      printf("[%d,%d] ",PQ[i].ele,PQ[i].pr); 
     printf("<-Rear"); 
    } 
} 

main() 
{       /* Main Program */ 
    int opn; 
    PriorityQ p; 
    do 
    { 
     printf("\n ### Priority Queue Operations(DSC order) ### \n\n"); 
     printf("\n Press 1-Insert, 2-Delete,3-Display,4-Exit\n"); 
     printf("\n Your option ? "); 
     scanf("%d",&opn); 
     switch(opn) 
     { 
     case 1: printf("\n\nRead the element and its Priority?"); 
      scanf("%d%d",&p.ele,&p.pr); 
      PQinsert(p.ele,p.pr); break; 
     case 2: p=PQdelete(); 
      if(p.ele != -1) 
       printf("\n\nDeleted Element is %d \n",p.ele); 
      break; 
     case 3: printf("\n\nStatus of Queue\n\n"); 
      display(); break; 
     case 4: printf("\n\n Terminating \n\n"); break; 
     default: printf("\n\nInvalid Option !!! Try Again !! \n\n"); 
      break; 
     } 
     printf("\n\n\n\n Press a Key to Continue . . . "); 
     getch(); 
    }while(opn != 4); 
} 

Answer 1

甲priority queue是一个数据结构保持元件（如任何数据结构），以及它们的优先级。这是你的第二个定义。

但是，在某些情况下，元素实际上代表了它们自己的优先级。这是你的第一个定义：有时，你只需要存储一堆无序数字并按顺序检索它们。请注意，在这种情况下，元素不一定是数字。其他数据类型可能具有可用作优先级的属性。