C言語のpriority_queueの使い方は?

2年 ago
綾乃, 一希
2 minutes

優先キューを実装するにはヒープデータ構造が必要で、ヒープとは次のような性質を持つ特別な2分木です。

  1. 親ノードの値は、子ノードの値よりも常に大きく（または小さく）なります。大規模ヒープでは、親ノードの値は子ノードの値以上で、小規模ヒープでは親ノードの値は子ノードの値以下となります。
  2. ヒープは常に完全2分木であり、つまり、最後の層を除くすべての層が一杯で、最後の層のノードはすべて左に配置されます。

C言語では、バイナリヒープを表すために配列を使用できます。最大ヒープの場合は、配列内の各要素が子ノードの値よりも大きくなります。最小ヒープの場合は、配列内の各要素が子ノードの値よりも小さくなります。

C言語での優先キューを使用する一般的な手順

  1. 配列と現在のヒープ内の要素の数を表す変数を保持するヒープ構造体を定義する。
#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int size;
} PriorityQueue;
  1. 挿入、堆の頂点の削除など、ヒープの基本的な操作をネイティブに実装。これら操作はヒープの性質（親ノードの値は子ノード以上）を維持する必要がある。
void insert(PriorityQueue* queue, int value) {
    if (queue->size >= MAX_SIZE) {
        printf("Priority queue is full.\n");
        return;
    }

    // 插入新元素到堆的最后
    int i = queue->size;
    queue->data[i] = value;

    // 调整堆，确保满足堆的性质
    while (i > 0 && queue->data[i] > queue->data[(i - 1) / 2]) {
        // 交换当前节点和父节点的值
        int temp = queue->data[i];
        queue->data[i] = queue->data[(i - 1) / 2];
        queue->data[(i - 1) / 2] = temp;
        i = (i - 1) / 2;  // 更新当前节点的索引
    }

    queue->size++;  // 更新堆的大小
}

int deleteMax(PriorityQueue* queue) {
    if (queue->size == 0) {
        printf("Priority queue is empty.\n");
        return -1;  // 表示空值或错误
    }

    int max = queue->data[0];  // 保存堆顶元素
    queue->size--;  // 更新堆的大小

    // 将最后一个元素移动到堆顶
    queue->data[0] = queue->data[queue->size];

    // 调整堆，确保满足堆的性质
    int i = 0;
    while (2 * i + 1 < queue->size) {
        int left = 2 * i + 1;  // 左子节点的索引
        int right = 2 * i + 2;  // 右子节点的索引
        int largest = i;  // 最大值的索引

        // 找到较大的子节点
        if (left < queue->size && queue->data[left] > queue->data[largest]) {
            largest = left;
        }
        if (right < queue->size && queue->data[right] > queue->data[largest]) {
            largest = right;
        }

        if (largest == i) {
            break;  // 已经满足堆的性质，退出循环
        }

        // 交换当前节点和较大子节点的值
        int temp = queue->data[i];
        queue->data[i] = queue->data[largest];
        queue->data[largest] = temp;

        i = largest;  // 更新当前节点的索引
    }

    return max;
}
  1. 優先キューを使ったコードサンプル:
int main() {
    PriorityQueue queue;
    queue.size = 0;

    insert(&queue, 5);
    insert
bannerAds