优先队列

原创

ge3m0r

发布于 2024-11-30 21:02:47

6600

代码可运行

文章被收录于专栏：数据结构与算法专栏数据结构与算法专栏

运行总次数：0

代码可运行

优先队列在很多语言中都是标准库中的函数,在 c++ 中引入使用 #include <queue>

#include  <queue>
#include <iostream>

using namespace std;
void main(){
    priority_queue<int> maxHeap
    // 调价
    maxHeap.push(123);
    maxHeap.push(456);
    while (!maxHeap.empty()) {
        cout << maxHeap.top() << " "; // 输出最大值
        maxHeap.pop();
    }
}

java 中也有对应的类

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        // 最小堆（默认）
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.add(10);
        minHeap.add(30);
        minHeap.add(20);

        System.out.println("最小堆：");
        while (!minHeap.isEmpty()) {
            System.out.print(minHeap.poll() + " "); // 输出最小值
        }
        System.out.println();

        // 最大堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        maxHeap.add(10);
        maxHeap.add(30);
        maxHeap.add(20);

        System.out.println("最大堆：");
        while (!maxHeap.isEmpty()) {
            System.out.print(maxHeap.poll() + " "); // 输出最大值
        }
    }
}

当然使用这个数据结构的函数就是最短源路径的 dijstria 算法.所以今天就先尝试实现一个函数.

show me the code

为了方便表示,这里默认优先队列里边保存的是 int, 并且优先队列是从小到大来排列数据,其实现就是一个简单的链表

struct PriorityQueue{
    int value;
    struct PriorityQueue* next;
}

优先队列的操作

struct PriorityQueue* create_node(int val){
    struct PriorityQueue* q = (struct Priority*) malloc(sizeof(struct PriorityQueue));
    if(q == NULL){
        printf("分配失败");
        return NULL;
    }
    q->value = val;
    q->next = NULL;
    return q;
}
void insert_node(struct PriorityQueue* queue, int val){
    struct PriorityQueue* q = create_node(val);
    if(queue == NULL){
        return q;
    }
    struct PriorityQueue* temp = queue;
    struct PriorityQueue* prev = queue;
    temp = temp -> next;
    if(queue->value > val){
        q->next = prev;
        queue = q;
        return queue;
    }
    while(temp != NULL){
        if(temp -> value > val){
            q->next = temp;
            prev->next = q;
            return queue;
        }
        temp = temp -> next;
        prev = prev->next;
    }
    // 如果是最大值
    prev->next = q;
    return queue;
}

// 函数中 top() 获取最顶端数据
int top(struct PriorityQueue* queue){
    if(queue == NULL) return -1;
    return queue->value;
}

// pop() 函数
void pop(struct PriorityQueue* queue){
    if(queue == NULL) printf("队列为空");
    struct PriorityQueue* temp = queue;
    queue = queue->next;
    free(temp);
}

上述基本上优先队列所有数据,比较简单,但是实现的话可以帮我回顾一下链表的操作,而且用 c 语言实现能理解的更深刻.

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

c 语言