優先級隊列的兩種不同定義？

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是一個數據結構保持元件（如任何數據結構），以及它們的優先級。這是你的第二個定義。

但是，在某些情況下，元素實際上代表了它們自己的優先級。這是你的第一個定義：有時，你只需要存儲一堆無序數字並按順序檢索它們。請注意，在這種情況下，元素不一定是數字。其他數據類型可能具有可用作優先級的屬性。