admin管理员组

文章数量:1624343

优先队列有点类似于队列，但有一个重要的区别:每个元素都以优先级级别添加到优先队列中，进行出队列操作时，具有最高优先级的元素将先出队列。也就是说，元素是按优先级顺序存储在队列中的，而不是按插入顺序存储的。

任务：
创建一个优先队列，必须至少支持两种操作：

  1. 入队列。 带有优先级（数字值）的元素添加到队列中。
  2. 队头出队列。 具有当前最高优先级的元素或元素之一出队并返回它。

可以定义其他操作，例如peek（查找当前的最高优先级/队头元素是什么），merge（将两个优先级队列合并为一个）等。

测试数据：

        Priority         Task
       ══════════   ════════════════
           3         Clear drains
           4         Feed cat
           5         Make tea
           1         Solve RC tasks
           2         Tax return

C

Using a dynamic array as a binary heap. Stores integer priority and a character pointer. Supports push and pop.

#include <stdio.h>
#include <stdlib.h>
 
typedef struct {
   
    int priority;
    char *data;
} node_t;
 
typedef struct {
   
    node_t *nodes;
    int len;
    int size;
} heap_t;
 
void push (heap_t *h, int priority, char *data) {
   
    if (h->len + 1 >= h->size) {
   
        h->size = h->size ? h->size * 2 : 4;
        h->nodes = (node_t *)realloc(h->nodes, h->size * sizeof (node_t));
    }
    int i = h->len + 1;
    int j = i / 2;
    while (i > 1 && h->nodes[j].priority > priority) {
   
        h->nodes[i] = h->nodes[j];
        i = j;
        j = j / 2;
    }
    h->nodes[i].priority = priority;
    h->nodes[i].data = data;
    h->len++;
}
 
char *pop (heap_t *h) {
   
    int i, j, k;
    if (!h->len) {
   
        return NULL;
    }
    char *data = h->nodes[1].data;
 
    h->nodes[1] = h->nodes[h->len];
 
    h->len--;
 
    i = 1;
    while (i!=h->len+1) {
   
        k = h->len+1;
        j = 2 * i;
        if (j <= h->len && h->nodes[j].priority < h->nodes[k].priority) {
   
            k = j;
        }
        if (j + 1 <= h->len && h->nodes[j + 1].priority < h->nodes[k].priority) {
   
            k = j + 1;
        }
        h->nodes[i] = h->nodes[k];
        i = k;
    }
    return data;
}
 
int main

本文标签： 队列PriorityQueue

版权声明：本文标题：优先队列（Priority queue） 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/dongtai/1728895475a1178352.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。