C言語の優先キューの使い方

2年 ago
桜, 春樹
2 minutes

C言語ではヒープを利用することで優先度付きキューを実装できます。ヒープとは以下の2つの性質を持つ特殊な二分木構造です。

  1. すべてのレベルに満たされたノードがあり、最後のレベルには左から順にノードが格納されています。
  2. 堆中任意节点的值都不大于（或不小于）其子节点的值。

次に、C言語で優先キューを実装したサンプルコードを示します。

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

// 定义优先队列结构
typedef struct {
    int *arr;  // 存储元素的数组
    int size;  // 队列的当前大小
    int capacity;  // 队列的最大容量
} PriorityQueue;

// 初始化优先队列
PriorityQueue* initPriorityQueue(int capacity) {
    PriorityQueue* queue = (PriorityQueue*)malloc(sizeof(PriorityQueue));
    queue->arr = (int*)malloc(sizeof(int) * (capacity + 1));
    queue->size = 0;
    queue->capacity = capacity;
    return queue;
}

// 交换元素
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 上浮操作
void swim(PriorityQueue* queue, int k) {
    while (k > 1 && queue->arr[k / 2] < queue->arr[k]) {
        swap(&(queue->arr[k / 2]), &(queue->arr[k]));
        k = k / 2;
    }
}

// 下沉操作
void sink(PriorityQueue* queue, int k) {
    while (2 * k <= queue->size) {
        int j = 2 * k;
        if (j < queue->size && queue->arr[j] < queue->arr[j + 1]) {
            j++;
        }
        if (queue->arr[k] >= queue->arr[j]) {
            break;
        }
        swap(&(queue->arr[k]), &(queue->arr[j]));
        k = j;
    }
}

// 插入元素
void insert(PriorityQueue* queue, int val) {
    if (queue->size == queue->capacity) {
        printf("Priority queue is full.\n");
        return;
    }
    queue->arr[++queue->size] = val;
    swim(queue, queue->size);
}

// 删除最大元素
int deleteMax(PriorityQueue* queue) {
    if (queue->size == 0) {
        printf("Priority queue is empty.\n");
        return -1;
    }
    int max = queue->arr[1];
    swap(&(queue->arr[1]), &(queue->arr[queue->size--]));
    sink(queue, 1);
    return max;
}

// 打印优先队列
void printPriorityQueue(PriorityQueue* queue) {
    printf("Priority Queue: ");
    for (int i = 1; i <= queue->size; i++) {
        printf("%d ", queue->arr[i]);
    }
    printf("\n");
}

int main() {
    PriorityQueue* queue = initPriorityQueue(10);
    insert(queue, 3);
    insert(queue, 10);
    insert(queue, 5);
    insert(queue, 1);

    printPriorityQueue(queue);

    int max = deleteMax(queue);
    printf("Delete max: %d\n", max);

    printPriorityQueue(queue);

    free(queue->arr);
    free(queue);
    return 0;
}

上のコードでは 配列を用いて優先キューの要素を格納しており 配列の先頭要素は使用 せ ず 配列の2番目以降の要素に要素を格納しています。 優先キューの性質を維持するため swim と sink の操作を行いました。 swim 操作は要素を挿入した後の 上昇操作で sink 操作は要素を削除した後の下降操作です。 insert 関数は要素の挿入に使用し deleteMax 関数は最大の要素の削除に使用します。 main 関数では 優先キューの使用方法を示しています。

bannerAds