# jh_priority_queue

**Repository Path**: arrco/jh_priority_queue

## Basic Information

- **Project Name**: jh_priority_queue
- **Description**: jh_priority_queue是一个基于堆实现的优先队列。可以实现任意数据结构任意排序方式的优先队列，例如最大堆，最小堆，根据优先级值排序的优先级队列等。

- **Primary Language**: C
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 5
- **Forks**: 1
- **Created**: 2022-02-06
- **Last Updated**: 2023-07-12

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# jh_priority_queue

## 介绍

jh_priority_queue是一个基于堆(heap)实现的优先队列。通过类似于标准库函数`qsort`的接口风格，实现任意数据结构任意排序方式的优先队列，例如最大堆，最小堆，根据优先级值排序的优先级队列等。

## 使用说明

只需要包含jh_priority_queue.c和jh_priority_queue.h两个文件即可使用。

## 接口函数

提供以下接口用于优先队列的使用：

```c
/*判断优先队列是否为空*/
int jh_priority_queue_is_empty(jh_priority_queue_t* pqueue);
/*判断优先队列是否已满*/
int jh_priority_queue_is_full(jh_priority_queue_t* pqueue);
/*获取优先队列的数据量*/
size_t jh_priority_queue_count(jh_priority_queue_t* pqueue);
/*优先队列入队*/
int jh_priority_queue_push(jh_priority_queue_t* pqueue, void* item);
/*优先队列出队*/
int jh_priority_queue_pop(jh_priority_queue_t* pqueue, void* item);
/*优先队列查看队首的数据*/
int jh_priority_queue_peek(jh_priority_queue_t* pqueue, void* item);
/*清空优先队列*/
int jh_priority_queue_clear(jh_priority_queue_t* pqueue);
/*优先队列初始化*/
int jh_priority_queue_init(jh_priority_queue_t* pqueue, void* base, size_t num, size_t size, int (*compare)(const void*, const void*));
```

另外还提供一个宏接口用于数据迭代：

```c
/*优先队列数据迭代*/
JH_PQUEUE_ITER(jh_priority_queue_t* pqueue, void* item)
```

## 接口使用说明

### 1.定义compare函数

首先需要定义一个用于比较两个数据项的compare函数。这个函数的实现方式影响着这个优先队列会以什么样的方式进行排序。

函数的类型为`int (*compare)(const void* p1, const void* p2)`。

函数返回值：

| 返回值 | 含义                    |
| --- | --------------------- |
| 非0  | p1指向的数据项排在在p2指向的数据项之前 |
| 0   | p1指向的数据项排在在p2指向的数据项之后 |

使用示例，假设保存的数据类型为int，按最大堆方式排序：

```c
int compare(const void * p1, const void * p2)
{
    return ( *(int*)p1 > *(int*)p2 );
}
```

### 2.优先队列初始化

调用接口`jh_priority_queue_init`初始化优先队列。

```c
/*优先队列初始化*/
int jh_priority_queue_int(jh_priority_queue_t* pqueue, void* base, size_t num, size_t size, int (*compare)(const void*, const void*));
```

函数参数含义：

| 参数      | 含义                                     |
| ------- | -------------------------------------- |
| pqueue  | 优先队列句柄，需要定义一个类型为jh_priority_queue_t的参数 |
| base    | 指向用于优先队列的数组                            |
| num     | 数组中能存放的数据项数量                           |
| size    | 数组中每个数据项的大小                            |
| compare | 指向用于比较两个数据项的函数指针                       |

函数返回值：

| 返回值 | 含义  |
| --- | --- |
| 0   | 成功  |
| -1  | 失败  |

使用示例：

```c
//定义数据结构和用于存放数据的数组
jh_priority_queue_t pqueue;
int buf[10];

//优先队列初始化
jh_priority_queue_init(&pqueue, buf, 10, sizeof(int), compare);
```

**注意**：初始化时传入值`num`，但实际可用于入队的数据数量为`num - 1`。例如上述的示例，定义用于存放数据的数组长度为10，但实际可以用于入队的数据数量为9。

### 3.优先队列入队

调用接口`jh_priority_queue_push`将数据放入队列中。

```c
/*优先队列入队*/
int jh_priority_queue_push(jh_priority_queue_t* pqueue, void* item);
```

函数参数含义：

| 参数     | 含义      |
| ------ | ------- |
| pqueue | 优先队列    |
| item   | 要入队的数据项 |

函数返回值：

| 返回值 | 含义  |
| --- | --- |
| 0   | 成功  |
| -1  | 失败  |

### 4.优先队列出队

调用接口`jh_priority_queue_pop`将数据从队列中取出。

```c
/*优先队列出队*/
int jh_priority_queue_pop(jh_priority_queue_t* pqueue, void* item);
```

函数参数含义：

| 参数     | 含义      |
| ------ | ------- |
| pqueue | 优先队列    |
| item   | 要出队的数据项 |

函数返回值：

| 返回值 | 含义  |
| --- | --- |
| 0   | 成功  |
| -1  | 失败  |

### 5.优先队列查看队首的数据

调用接口`jh_priority_queue_peek`查看优先队列队首的数据。

```c
/*优先队列查看队首的数据*/
int jh_priority_queue_peek(jh_priority_queue_t* pqueue, void* item);
```

函数参数含义：

| 参数     | 含义     |
| ------ | ------ |
| pqueue | 优先队列   |
| item   | 队首的数据项 |

函数返回值：

| 返回值 | 含义  |
| --- | --- |
| 0   | 成功  |
| -1  | 失败  |

### 6.获取优先队列的数据数量

调用接口`jh_priority_queue_count`查看优先队列中已有的数据数量。

```c
/*获取优先队列的数据量*/
size_t jh_priority_queue_count(jh_priority_queue_t* pqueue);
```

函数参数含义：

| 参数     | 含义   |
| ------ | ---- |
| pqueue | 优先队列 |

函数返回值：

| 返回值 | 含义               |
| ------ | ------------------ |
| >=0    | 优先队列的数据数量 |

### 7.判断优先队列是否已满

调用接口`jh_priority_queue_is_full`判断优先队列是否已满。

```c
/*判断优先队列是否已满*/
int jh_priority_queue_is_full(jh_priority_queue_t* pqueue);
```

函数参数含义：

| 参数     | 含义   |
| ------ | ---- |
| pqueue | 优先队列 |

函数返回值：

| 返回值 | 含义     |
| --- | ------ |
| 1   | 优先队列已满 |
| 0   | 优先队列未满 |
| -1  | 失败     |

**注意**：优先队列可用于入队的最大数据数量为`num - 1`，`num`指的是在初始化时调用接口`jh_priority_queue_init`时设置的`num`。

### 8.判断优先队列是否为空

调用接口`jh_priority_queue_is_empty`判断优先队列是否为空。

```c
/*判断优先队列是否为空*/
int jh_priority_queue_is_empty(jh_priority_queue_t* pqueue);
```

函数参数含义：

| 参数     | 含义   |
| ------ | ---- |
| pqueue | 优先队列 |

函数返回值：

| 返回值 | 含义      |
| --- | ------- |
| 1   | 优先队列为空  |
| 0   | 优先队列不为空 |
| -1  | 失败      |

### 9.清空优先队列

调用接口`jh_priority_queue_clear`清空优先队列。

```c
/*清空优先队列*/
int jh_priority_queue_clear(jh_priority_queue_t* pqueue);
```

函数参数含义：

| 参数     | 含义   |
| ------ | ---- |
| pqueue | 优先队列 |

函数返回值：

| 返回值 | 含义  |
| --- | --- |
| 0   | 成功  |
| -1  | 失败  |

### 10.优先队列数据迭代

调用接口`JH_PQUEUE_ITER`进行数据迭代。

```c
JH_PQUEUE_ITER(jh_priority_queue_t* pqueue, void* item)
```

函数参数含义：

| 参数     | 含义   |
| ------ | ---- |
| pqueue | 优先队列 |
| item   | 数据项  |

使用示例，打印出当前优先队列中的所有数据：

```c
JH_PQUEUE_ITER(&pqueue, &val) {
    printf("val : %d\n", val);
}
```

**注意**：迭代的顺序是按照存储数据的顺序，不是按`compare`函数制定的排序规则。

## 使用示例

下面提供几个最基本的使用示例：

### 1.最大堆

实现一个最大堆：

```c
int compare(const void * a, const void * b)
{
    //使用>号，实现的是最大堆
    return ( *(int*)a > *(int*)b );
}

int main(int argc, char* argv[])
{
    //定义数据结构和用于存放数据的数组
    jh_priority_queue_t pqueue;
    int buf[10];

    //优先队列初始化
    jh_priority_queue_init(&pqueue, buf, 10, sizeof(int), compare);

    //定义要用于传入的数据
    int items[] = {81, 13, 16, 38, 49, 67};
    int i, val;

    //数据入队
    printf("\npush:\n");
    for(i = 0; i < sizeof(items)/sizeof(int); i++) {
        if(!jh_priority_queue_push(&pqueue, &items[i]))
            printf("%d ", items[i]);
    }
    printf("\n");

    //数据出队
    printf("\npop:\n");
    for(i = 0; i < sizeof(items)/sizeof(int); i++) {
        if(!jh_priority_queue_pop(&pqueue, &val))
            printf("%d ", val);
    }
    printf("\n");

    return 0;
}
```

运行结果如下：

```shell
push:
81 13 16 38 49 67 

pop:
81 67 49 38 16 13 
```

### 2.最小堆

实现一个最小堆，代码和最大堆一样，只需要修改`compare`函数中的比较方式就变成了最小堆。

```c
int compare(const void * a, const void * b)
{
    //使用<号，实现的是最小堆
    return ( *(int*)a < *(int*)b );
}
```

运行结果如下：

```shell
push:
81 13 16 38 49 67 

pop:
13 16 38 49 67 81 
```

### 3.优先级队列

实现一个根据优先级值来判断优先级高低的优先级队列。

```c
//自定义数据结构
typedef struct {
    int data;       //数据
    int priority;   //优先级
} my_priority_data_t;

int compare(const void * a, const void * b)
{
    //将优先级值最小，优先级最高的数据放在队头
    return ( ((my_priority_data_t*)a)->priority < ((my_priority_data_t*)b)->priority );
}

int main(int argc, char* argv[])
{
    //定义数据结构和用于存放数据的数组
    jh_priority_queue_t pqueue;
    my_priority_data_t buf[10];

    //优先队列初始化
    jh_priority_queue_init(&pqueue, buf, 10, sizeof(my_priority_data_t), compare);

    //定义要用于传入的数据
    my_priority_data_t items[] = {{81, 6}, {13, 3}, {16, 5}, {38, 4}, {49, 1}, {67, 2}};
    my_priority_data_t val;
    int i;

    //数据入队
    printf("\npush:\n");
    for(i = 0; i < sizeof(items)/sizeof(my_priority_data_t); i++) {
        if(!jh_priority_queue_push(&pqueue, &items[i]))
            printf("data %d priority %d\n", items[i].data, items[i].priority);
    }
    printf("\n");

    //查看当前的状态
    printf("count : %d empty : %d full : %d\n", jh_priority_queue_count(&pqueue), jh_priority_queue_is_empty(&pqueue), jh_priority_queue_is_full(&pqueue));

    //数据出队
    printf("\npop:\n");
    for(i = 0; i < sizeof(items)/sizeof(int); i++) {
        if(!jh_priority_queue_pop(&pqueue, &val))
            printf("data %d priority %d\n", val.data, val.priority);
    }
    printf("\n");

    //查看当前的状态
    printf("count : %d empty : %d full : %d\n", jh_priority_queue_count(&pqueue), jh_priority_queue_is_empty(&pqueue), jh_priority_queue_is_full(&pqueue));

    return 0;
}
```

运行结果如下：

```shell
push:
data 81 priority 6
data 13 priority 3
data 16 priority 5
data 38 priority 4
data 49 priority 1
data 67 priority 2

count : 6 empty : 0 full : 0

pop:
data 49 priority 1
data 67 priority 2
data 13 priority 3
data 38 priority 4
data 16 priority 5
data 81 priority 6

count : 0 empty : 1 full : 0
```

## License

MIT License

Copyright (c) 2022 Hong Jiahua

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.