堆排序是一個比較優(yōu)秀的算法,堆這種數(shù)據(jù)結構在現(xiàn)實生活中有很多的應用,比如堆可以作為一個優(yōu)先隊列來使用,作為一個高效的優(yōu)先隊列,它與堆的結構一樣,都有最大優(yōu)先隊列,最小優(yōu)先隊列.優(yōu)先隊列priority queue 是一種用來維護一組元素構成的集合S的數(shù)據(jù)結構，每一個元素都有一個相關的值，稱為關鍵字(key)。

最大優(yōu)先隊列包含以下操作：

將元素x插入到S的集合中，等價于

；

返回S中最大元素；

返回并且刪除S中最大元素；

將元素x的關鍵字增加到key，要求

。

同樣的，最小優(yōu)先隊列操作也包括：

,

,

,

。只不過是對最小值進行操作。

在這里主要討論最大優(yōu)先隊列，其應用很多，在共享計算機作業(yè)系統(tǒng)就是，類似于早期的unix主機，管理員root可以設置n個不同的用戶，以及各個用戶不同的操作權限，從主機那里接出多個終端，每個操作人員(程序員)在自己的工作終端 ，感覺像是自己擁有自己獨立的作業(yè)主機一樣，其實不是，通過一些任務調度來實現(xiàn)，其中就有任務等待執(zhí)行相關隊列，并且有各個任務有著自己優(yōu)先級，以便確定調度執(zhí)行具體任務，如果你學過操作系統(tǒng)相關知識，那么應該對系統(tǒng)調度有所了解。

當一個作業(yè)被完成或者被中斷后，調度器會調用

來調用所有在隊列中等待任務中優(yōu)先級最高的任務執(zhí)行，在新任務加入等待任務時會調用

加入任務等待隊列，當某個任務等待時間過長時可通過

提高其優(yōu)先級，從而減少等待時間。

下面是具體實現(xiàn)C程序源碼：

#include

#define NAGE_INFINIT -99999

#define parent(i) i/2

#define left(i) 2*i+1

#define right(i) 2*i+2

//get array of A first element

int heap_maximum(int A[]){ return A[0];}

/***********************************************

*

* function max_heapify();

*

* args

*? A[] inttype save elements of heap

*? i index of A

*? heap_size real length of A

*

* ********************************************/

void max_heapify(int A[],int i,int heap_size){

int l,r,largest,temp;

l=left(i);

r=right(i);

if((l<=heap_size)&&(A[l]>A[i]))

largest=l;

else

largest=i;

if((r<=heap_size)&&(A[r]>A[largest]))

largest=r;

if(largest!=i){

temp=A[i];

A[i]=A[largest];

A[largest]=temp;

max_heapify(A,largest,heap_size);

}

}

/*********************************************

*

* function heap_extract_max()

*

* args

*? A[] inttype save elements of heap

*? heap_size inttype the real length of A

*

* return max the parent node value

*

* ******************************************/

int heap_extract_max(int A[],int heap_size){

int max;

if(heap_size<0)

return -1;? //heap underflow

max=A[0];? //parent node the max value of element

A[0]=A[heap_size];

heap_size--;

/**************************************

* dajust binary heap(or tree) to make

* sure heap fo A true every times

*

* ************************************/

max_heapify(A,0,heap_size);

return max;

}

/***********************************************

*

* function heap_increase_key();

*

* args

*? A[] inttype save elemnts of heap

*? i index of A

*? key inserted element

*

* *********************************************/

void heap_increase_key(int A[],int i,int key){

int temp;

if(key

printf("new key is smaller than current key\n");

return;? ? //over programming

}

A[i]=key;

//p=parent(i);

while ((i>0)&&(A[parent(i)]

總結

以上是生活随笔為你收集整理的C语言优先队列作用,C语言实现优先队列(priority queue)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。