304 优先队列

优先队列

优先队列是一种特殊的队列，元素按照优先级顺序出队，优先级高的元素先出。常见且高效的实现方式是基于堆（Heap）数据结构，堆可以是最大堆（Max-Heap）或最小堆（Min-Heap），分别实现最大优先队列或最小优先队列。

优先队列的基本操作

• 插入（insert / push）：将元素插入队列，维护堆的性质。
• 取出最高优先级元素（pop）：删除并返回优先级最高的元素（最大堆中是最大元素，最小堆中是最小元素）。
• 查看最高优先级元素（peek / top）：返回优先级最高的元素但不删除。
• 判空（isEmpty）：判断队列是否为空。

常见实现方式

实现方式	插入复杂度	删除复杂度	说明
无序数组	O(1)	O(n)	插入快，删除慢
有序数组	O(n)	O(1)	插入慢，删除快
链表	O(1)	O(n)	类似无序数组
二叉搜索树	O(log n)	O(log n)	平衡树实现较复杂
堆（推荐）	O(log n)	O(log n)	插入和删除都高效，常用实现

C 语言实现

 
#include <stdio.h>
#include <stdlib.h>
 
typedef struct {
    int *data;      // 存储堆元素的数组
    int capacity;   // 堆容量
    int size;       // 当前堆中元素个数
} MinHeap;
 
// 交换两个元素
void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
 
// 初始化堆，capacity为最大容量
MinHeap* heap_init(int capacity) {
    MinHeap *heap = (MinHeap*)malloc(sizeof(MinHeap));
    if (!heap) return NULL;
    heap->data = (int*)malloc(sizeof(int) * capacity);
    if (!heap->data) {
        free(heap);
        return NULL;
    }
    heap->capacity = capacity;
    heap->size = 0;
    return heap;
}
 
// 上浮操作：插入元素后调整堆
void heapify_up(MinHeap *heap, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (heap->data[parent] <= heap->data[index]) {
            break;
        }
        swap(&heap->data[parent], &heap->data[index]);
        index = parent;
    }
}
 
// 下沉操作：删除堆顶后调整堆
void heapify_down(MinHeap *heap, int index) {
    int left, right, smallest;
    while (1) {
        left = 2 * index + 1;
        right = 2 * index + 2;
        smallest = index;
 
        if (left < heap->size && heap->data[left] < heap->data[smallest]) {
            smallest = left;
        }
        if (right < heap->size && heap->data[right] < heap->data[smallest]) {
            smallest = right;
        }
        if (smallest == index) {
            break;
        }
        swap(&heap->data[index], &heap->data[smallest]);
        index = smallest;
    }
}
 
// 插入元素，返回0成功，-1失败（堆满）
int heap_push(MinHeap *heap, int val) {
    if (heap->size >= heap->capacity) {
        return -1; // 堆满
    }
    heap->data[heap->size] = val;
    heapify_up(heap, heap->size);
    heap->size++;
    return 0;
}
 
// 弹出堆顶元素，返回堆顶，堆空时返回-1（也可用其他标记）
int heap_pop(MinHeap *heap) {
    if (heap->size == 0) {
        return -1; // 堆空
    }
    int ret = heap->data[0];
    heap->data[0] = heap->data[heap->size - 1];
    heap->size--;
    heapify_down(heap, 0);
    return ret;
}
 
// 获取堆顶元素，不弹出，堆空时返回-1
int heap_top(MinHeap *heap) {
    if (heap->size == 0) {
        return -1;
    }
    return heap->data[0];
}
 
// 判空
int heap_is_empty(MinHeap *heap) {
    return heap->size == 0;
}
 
// 释放堆内存
void heap_free(MinHeap *heap) {
    if (heap) {
        free(heap->data);
        free(heap);
    }
}
 
// 测试示例
int main() {
    MinHeap *pq = heap_init(100);
    if (!pq) {
        printf("Heap init failed\n");
        return -1;
    }
 
    int arr[] = {5, 3, 8, 1, 9, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
 
    for (int i = 0; i < n; i++) {
        heap_push(pq, arr[i]);
        printf("Inserted %d, top now: %d\n", arr[i], heap_top(pq));
    }
 
    printf("Pop all elements in order:\n");
    while (!heap_is_empty(pq)) {
        printf("%d ", heap_pop(pq));
    }
    printf("\n");
 
    heap_free(pq);
    return 0;
}

说明

• 堆用数组实现，根节点索引为 0。
• 插入元素时，放到数组末尾，执行 heapify_up 上浮调整，保证最小堆性质。
• 弹出堆顶元素时，用最后一个元素替换堆顶，执行 heapify_down 下沉调整。
• 所有操作时间复杂度均为 O(log⁡n)O(logn)。
• 该实现为最小堆优先队列，优先级高的元素值更小。