c++最小堆dequeue

以下是使用C++ STL中的priority_queue实现最小堆的例子：

#include <iostream>
#include <queue>
#include <vector>
#include <functional>

using namespace std;

int main() {
    // 构造小堆，需要给第三个模板参数传仿函数类greater
    priority_queue<int, vector<int>, greater<int>> pq;

    pq.push(4);
    pq.push(1);
    pq.push(7);
    pq.push(6);
    pq.push(2);
    pq.push(5);

    // 遍历优先级队列中的元素
    while (!pq.empty()) {
        cout << pq.top() << " "; // 堆顶元素
        pq.pop();
    }
    // 输出：1 2 4 5 6 7

    return 0;
}

在上述代码中，我们使用了STL中的priority_queue容器，并通过传递仿函数greater<int>来实现最小堆。在将元素插入到堆中后，我们遍历堆并输出堆顶元素，直到堆为空。

相关问题

C++优先队列实现二叉堆

C语言中实现优先队列的经典方式是使用二叉堆数据结构。二叉堆是一种完全二叉树，同时满足堆次序的条件。在二叉堆中，每个节点的值都大于或等于其子节点的值（最大堆），或者每个节点的值都小于或等于其子节点的值（最小堆）。通过维护堆次序，可以保证堆顶元素是最大或最小的元素。

下面是C语言中实现二叉堆的优先队列的一种方法：

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

typedef struct {
    int capacity;  // 队列的容量
    int size;      // 队列中元素的数量
    int *data;     // 存储队列元素的数组
} PriorityQueue;

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

void destroyPriorityQueue(PriorityQueue *queue) {
    free(queue->data);
    free(queue);
}

void enqueue(PriorityQueue *queue, int value) {
    if (queue->size >= queue->capacity) {
        // 队列已满，需要扩容
        queue->capacity *= 2;
        queue->data = (int*)realloc(queue->data, sizeof(int) * queue->capacity);
    }
    // 将元素放入队列尾部
    queue->data[queue->size] = value;
    queue->size++;
    // 通过向上调整操作恢复堆次序
    int child = queue->size - 1;
    int parent = (child - 1) / 2;
    while (child > 0 && queue->data[child] > queue->data[parent]) {
        int temp = queue->data[child];
        queue->data[child] = queue->data[parent];
        queue->data[parent] = temp;
        child = parent;
        parent = (child - 1) / 2;
    }
}

int dequeue(PriorityQueue *queue) {
    int value = queue->data[0];
    // 将队尾元素放到队首，并删除队尾元素
    queue->data[0] = queue->data[queue->size - 1];
    queue->size--;
    // 通过向下调整操作恢复堆次序
    int parent = 0;
    while (parent * 2 + 1 < queue->size) {
        int leftChild = parent * 2 + 1;
        int rightChild = parent * 2 + 2;
        int maxChild = leftChild;
        if (rightChild < queue->size && queue->data[rightChild] > queue->data[leftChild]) {
            maxChild = rightChild;
        }
        if (queue->data[parent] >= queue->data[maxChild]) {
            break;
        }
        int temp = queue->data[parent];
        queue->data[parent] = queue->data[maxChild];
        queue->data[maxChild] = temp;
        parent = maxChild;
    }
    return value;
}

int main() {
    PriorityQueue *queue = createPriorityQueue(10);
    enqueue(queue, 5);
    enqueue(queue, 3);
    enqueue(queue, 7);
    printf("%d\n", dequeue(queue));  // 输出7，因为7是队列中的最大值
    printf("%d\n", dequeue(queue));  // 输出5，因为5是队列中的次大值
    printf("%d\n", dequeue(queue));  // 输出3，因为3是队列中的最小值
    destroyPriorityQueue(queue);
    return 0;
}

数据结构 c++plus实现

下面是一些常见的数据结构，以及它们在 C++ 中的实现：

1. 数组

C++ 中的数组是一组相同类型的元素的集合，可以通过下标来访问数组中的元素。下面是一个创建和初始化数组的示例：

int arr[5];        // 声明一个包含5个整数的数组
arr[0] = 1;        // 设置第一个元素为1
arr[1] = 2;        // 设置第二个元素为2
arr[2] = 3;        // 设置第三个元素为3
arr[3] = 4;        // 设置第四个元素为4
arr[4] = 5;        // 设置第五个元素为5

2. 链表

链表是一种动态数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。下面是一个简单的链表实现：

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 创建一个链表，并添加一些元素
ListNode* head = new ListNode(1);
ListNode* second = new ListNode(2);
ListNode* third = new ListNode(3);
head->next = second;
second->next = third;

3. 栈

栈是一种后进先出（LIFO）的数据结构，它支持两个基本操作：push（将元素压入栈顶）和pop（将栈顶元素弹出）。下面是一个简单的栈实现：

class Stack {
public:
    Stack() {}
    void push(int x) {
        st.push(x);
    }
    void pop() {
        st.pop();
    }
    int top() {
        return st.top();
    }
    bool empty() {
        return st.empty();
    }
private:
    std::stack<int> st;
};

// 创建一个栈，并添加一些元素
Stack s;
s.push(1);
s.push(2);
s.push(3);
s.pop();    // 弹出栈顶元素

4. 队列

队列是一种先进先出（FIFO）的数据结构，它支持两个基本操作：enqueue（将元素插入队尾）和dequeue（将队头元素弹出）。下面是一个简单的队列实现：

class Queue {
public:
    Queue() {}
    void enqueue(int x) {
        q.push(x);
    }
    void dequeue() {
        q.pop();
    }
    int front() {
        return q.front();
    }
    bool empty() {
        return q.empty();
    }
private:
    std::queue<int> q;
};

// 创建一个队列，并添加一些元素
Queue q;
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
q.dequeue();    // 弹出队头元素

5. 堆

堆是一种完全二叉树，它满足堆属性：对于每个节点 x，其父节点的值小于或等于 x 的值（最大堆）或大于或等于 x 的值（最小堆）。在 C++ 中，可以使用 priority_queue 类来实现堆：

class Heap {
public:
    Heap() {}
    void push(int x) {
        pq.push(x);
    }
    void pop() {
        pq.pop();
    }
    int top() {
        return pq.top();
    }
    bool empty() {
        return pq.empty();
    }
private:
    std::priority_queue<int> pq;
};

// 创建一个最大堆，并添加一些元素
Heap h;
h.push(1);
h.push(3);
h.push(2);
h.pop();    // 弹出堆顶元素