Приоритетная очередь в языке программирования C

Класс priority queue (очередь с приоритетом) в языке программирования C является важной структурой данных, которая позволяет хранить элементы с определенным приоритетом. Элементы в этой структуре данных упорядочены по их приоритету, и обеспечивается быстрый доступ к элементу с самым высоким приоритетом.

В C, реализация priority queue обычно основана на двоичной куче (binary heap). Двоичная куча является внешней формой двоичного поискового дерева, где каждый узел имеет не более двух детей. Для удобства, мы можем использовать указатели на узлы, чтобы представлять двоичную кучу.

Рассмотрим пример реализации приоритетной очереди на C с использованием двоичной кучи:

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int priority;
    int value;
} Node;

typedef struct PriorityQueue {
    Node** heap;
    int capacity;
    int size;
} PriorityQueue;

PriorityQueue* createPriorityQueue(int capacity) {
    PriorityQueue* queue = malloc(sizeof(PriorityQueue));
    queue->capacity = capacity;
    queue->size = 0;
    queue->heap = malloc(sizeof(Node*) * capacity);
    return queue;
}

void enqueue(PriorityQueue* queue, int priority, int value) {
    if (queue->size >= queue->capacity) {
        printf("Priority queue is full.\n");
        return;
    }
    Node* newNode = malloc(sizeof(Node));
    newNode->priority = priority;
    newNode->value = value;
    
    int currentIndex = queue->size;
    int parentIndex = (currentIndex - 1) / 2;
    
    while (currentIndex > 0 && queue->heap[parentIndex]->priority < newNode->priority) {
        queue->heap[currentIndex] = queue->heap[parentIndex];
        currentIndex = parentIndex;
        parentIndex = (currentIndex - 1) / 2;
    }
    
    queue->heap[currentIndex] = newNode;
    queue->size++;
}

Node* dequeue(PriorityQueue* queue) {
    if (queue->size == 0) {
        printf("Priority queue is empty.\n");
        return NULL;
    }
    Node* result = queue->heap[0];
    Node* lastNode = queue->heap[queue->size - 1];
    queue->size--;
    
    int currentIndex = 0;
    int childIndex = 1;
    
    while (childIndex < queue->size) {
        if ((childIndex + 1) < queue->size && queue->heap[childIndex + 1]->priority > queue->heap[childIndex]->priority) {
            childIndex++;
        }
        if (lastNode->priority >= queue->heap[childIndex]->priority) {
            break;
        }
        
        queue->heap[currentIndex] = queue->heap[childIndex];
        currentIndex = childIndex;
        childIndex = (currentIndex * 2) + 1;
    }
    
    queue->heap[currentIndex] = lastNode;
    return result;
}

void destroyPriorityQueue(PriorityQueue* queue) {
    for (int i = 0; i < queue->size; i++) {
        free(queue->heap[i]);
    }
    free(queue->heap);
    free(queue);
}

int main() {
    PriorityQueue* queue = createPriorityQueue(10);
    
    enqueue(queue, 5, 10);
    enqueue(queue, 1, 20);
    enqueue(queue, 3, 30);
    
    Node* node = dequeue(queue);
    printf("%d ", node->value);
    free(node);
    
    node = dequeue(queue);
    printf("%d ", node->value);
    free(node);
    
    node = dequeue(queue);
    printf("%d ", node->value);
    free(node);
    
    destroyPriorityQueue(queue);
    
    return 0;
}

В приведенном выше коде мы определяем структуры Node и PriorityQueue. Структура Node представляет узел, содержащий приоритет и значение элемента. Структура PriorityQueue представляет саму приоритетную очередь и включает в себя указатель на двоичную кучу, емкость, текущий размер и другие необходимые переменные.

Мы создаем функцию createPriorityQueue для создания новой приоритетной очереди заданной емкости. Функция enqueue используется для добавления элемента в очередь с указанным приоритетом и значением. Функция dequeue удаляет элемент с наивысшим приоритетом из очереди и возвращает указатель на узел.

В функции main мы создаем новую приоритетную очередь и добавляем несколько элементов с разными приоритетами и значениями. Затем мы последовательно удаляем элементы из очереди с помощью функции dequeue и выводим их значения.

В конце мы освобождаем память, выделенную для очереди и элементов.

Это простой пример реализации приоритетной очереди на C с использованием двоичной кучи. Конечно, существуют и другие способы реализации priority queue, включая использование массивов, связанных списков и т.д. В зависимости от ваших конкретных требований и ограничений, вы можете выбрать наиболее подходящую реализацию.