---
# System prepended metadata

title: priority_queue.a 優先權佇列使用說明書

---

# <center><font size=10>priority_queue.a</font> <br> <font size=5>優先權佇列使用說明書</font> <br> <font size=4>by 李奕承</font></center>

# <center>摘要</center>
本library提供的結構如下

```c
typedef struct HeapType {
    void * elements;
    int numElementds;
}Heap_t;

typedef enum {
    MINHEAP = 0,
    MAXHEAP
}H_class;

// 使用者會操作的
typedef struct PQ {
    H_class pqClass;
    Heap_t heap;
    int maxSize;
    int elementSize;
    int (*compare)(void * elementA, void * elementB);
}PQ_t;
```

本 library 使用陣列跟index換算來模擬二元樹的走訪，並提供以下幾種函數
- 產生優先權佇列
- 判斷優先權佇列是否為空
- 以完全二元樹印出優先權佇列
- 插入
- 計算優先權佇列Level
- 判斷優先權佇列是否已滿
- 取出




# <center>使用方法</center>
### 1.帶入標頭檔
```c
#include"pqSpec.h"
```

### 2.創造 priority queue
宣告一個 PQ_t ，使用 createPQ() 填入PQ_t的各項設定，例如：
```c
PQ_t first_pq;
createPQ(&first_pq, MINHEAP, 10, compareMath);
```
first_pq : 是優先權佇列的指標
MINHEAP : 是枚舉值，代表值越小的優先
10 : 是資料的數量，本 priority queue 在創建時會申請一塊固定大小的記憶體作為指標陣列
compareMath : 是用來比較值的函數，由使用者編寫並提供函數指標

### 3.編寫並提供回調函數指標
以下兩個需要使用者編寫並提供回調函數指標
```c
 createPQ
 pq_printf_tree
```

### 4.編譯
- pqSpec.h 要記得放在引用標頭檔的路徑下
- 編譯時記得加入 priority_queue.a
```
gcc -I include -Wall -o ./bin/test test.c priority_queue.a
```


# <center>函數介紹與範例</center>
## 範例使用的結構
下面是範例用到的結構
```c
typedef struct test_element {
    char ID[10];
    int math;
    int eng;
}student_t;
```
下面是範例中使用者提供給 libary 用來比較 priority 的函數
```c
int compareMath(void* elementA, void* elementB)
{
    if(((student_t *)elementA)->math > ((student_t *)elementB)->math)
    {
        return 1;
    }
    else if(((student_t *)elementA)->math < ((student_t *)elementB)->math)
    {
        return -1;
    }
    return 0;
}
```
下面範例中使用者用來取出元素中數值的函數
```clike
char* get_math(void* element)
{
    static char buffer[20];
    sprintf(buffer, "%d", ((student_t*)element)->math);
	return buffer;
}
```

## 產生優先權佇列
```clike
void createPQ(PQ_t* pq, H_class pqClass, int maxSize, 
              int(*compare)(void* elementA, void* elementB));
```
當你宣告一個 PQ_t 之後，要使用這個函數來設定 PQ_t 中需要用到的值

其中包括 PQ_t 的地址、Heap的類型(最大或最小)、priority queue 容納的上限、用來比較 priority 的函數(由使用者提供)，以下是範例。
```clike
PQ_t first_pq;
createPQ(&first_pq, MINHEAP, 10, compareMath);
```

## 判斷優先權佇列是否為空
```clike
int IsEmpty(PQ_t* pq);
```
使用這個函數可以判斷 priority queue 是否為空，以下是範例。
```clike
printf("is queue empty? 0->true 1->false : %d\n", IsEmpty(&first_pq));
```
終端機的輸出
```
is queue empty? 0->true 1->false : 0
```

## 以完全二元樹印出優先權佇列
```clike
void pq_printf_tree(PQ_t* pq, char*(*get_data)(void* queue_member));
```
使用這個函數可以將 priority queue 以完全二元樹的形式印出來，便於除錯，以下是範例

```clike
pq_printf_tree(&first_pq, get_math);
```
終端機的輸出可以在後續的敘述中看到

## 插入
```clike
int Enqueue(PQ_t* pq, void* elementA);
```
使用這個函數可以在 priority queue 中加入新的元素，以下是範例。
```clike
student_t node[10] = {
    {"A", 70, 100},
    {"B", 60, 90},
    {"C", 80, 95},
    {"D", 65, 90},
    {"E", 10, 70},
    {"F", 90, 90},
    {"G", 20, 60},
    {"H", 30, 50},
    {"I", 40, 40},
    {"J", 50, 30}
};

for(int i = 0 ; i < 10 ; i++)
{
    Enqueue(&first_pq, &node[i]);
    pq_printf_tree(&first_pq, get_math);
}
```
終端機的輸出

```
 70

  60   
  /    
 /     
70     

  60   
  / \  
 /   \ 
70   80

      60       
      / \      
     /   \
    /     \
   65     80
  /
 /
70

      10
      / \
     /   \
    /     \
   60     80   
  / \
 /   \
70   65

      10
      / \
     /   \
    /     \
   60     80
  / \     /
 /   \   /
70   65 90

      10
      / \
     /   \
    /     \
   60     20
  / \     / \
 /   \   /   \
70   65 90   80

              10
              / \
             /   \
            /     \
           /       \
          /         \
         /           \
        /             \
       30             20
      / \             / \
     /   \           /   \
    /     \         /     \
   60     65       90     80
  /
 /
70

              10
              / \
             /   \
            /     \
           /       \
          /         \
         /           \
        /             \
       30             20
      / \             / \
     /   \           /   \     
    /     \         /     \
   40     65       90     80
  / \
 /   \
70   60

              10
              / \
             /   \
            /     \
           /       \
          /         \
         /           \
        /             \
       30             20       
      / \             / \
     /   \           /   \
    /     \         /     \
   40     50       90     80
  / \     /
 /   \   /
70   60 65
```



## 計算Level
```clike
int count_pq_level(PQ_t* pq);
```
使用這個函數可以算出 priority queue 的Level數，以下是範例。
```clike
pq_printf_tree(&first_pq, get_math);
printf("the tree level is : %d\n", count_pq_level(&first_pq));
```

```
              10
              / \
             /   \
            /     \
           /       \
          /         \
         /           \
        /             \
       30             20
      / \             / \
     /   \           /   \
    /     \         /     \
   40     50       90     80
  / \     /
 /   \   /
70   60 65

the tree level is : 3
```




## 判斷是否已滿
```clike
int IsFull(PQ_t* pq);
```
使用這個函數可以判斷 priority queue 是否已滿，以下是範例。
```clike
printf("is queue full? 0->true 1->false : %d\n", IsFull(&first_pq));
```
終端機的輸出
```
is queue full? 0->true 1->false : 0
```


## 取出
```clike
void* Dequeue(PQ_t* pq);
```
使用這個函數可以在 priority queue 中取出最上層的元素，以下是範例。
```clike
pq_printf_tree(&first_pq, get_math);

for(int i = 0 ; i<10 ; i++)
{
    printf("-----------------------------------------\n");
    printf("get : %s\n", get_math(Dequeue(&second_pq)));      
    pq_printf_tree(&second_pq, get_math);
}
```
終端機的輸出
```
              10
              / \
             /   \
            /     \
           /       \
          /         \
         /           \
        /             \
       30             20
      / \             / \
     /   \           /   \
    /     \         /     \
   40     50       90     80
  / \     /
 /   \   /
70   60 65
-----------------------------------------
get : 10

              20
              / \
             /   \
            /     \
           /       \
          /         \
         /           \
        /             \
       30             65
      / \             / \
     /   \           /   \
    /     \         /     \
   40     50       90     80
  / \
 /   \
70   60
-----------------------------------------
get : 20

              30
              / \
             /   \
            /     \
           /       \
          /         \
         /           \
        /             \
       40             65
      / \             / \
     /   \           /   \
    /     \         /     \
   60     50       90     80
  /
 /
70
-----------------------------------------
get : 30

      40
      / \      
     /   \
    /     \
   50     65
  / \     / \
 /   \   /   \
60   70 90   80
-----------------------------------------
get : 40

      50
      / \
     /   \
    /     \
   60     65
  / \     /
 /   \   /
80   70 90
-----------------------------------------
get : 50

      60
      / \
     /   \
    /     \
   70     65
  / \
 /   \
80   90
-----------------------------------------
get : 60

      65
      / \
     /   \     
    /     \
   70     90
  /
 /
80
-----------------------------------------
get : 65

  70
  / \
 /   \
80   90
-----------------------------------------
get : 70

  80
  /
 /
90
-----------------------------------------
get : 80

 90
-----------------------------------------
get : 90

```



