C++容器：priority_queue的优先级队列详解

# 章节一：C容器简介

C++是一种多范式编程语言，它提供了许多容器类，包括vector、list、queue和stack等。在这些容器中，优先级队列（priority_queue）是一个非常有用的工具，它能够自动将元素进行排序，使得队首元素始终是最大（或最小）的元素。在本章中，我们将了解C++中优先级队列的使用方法以及底层实现原理。
### 章节二：priority_queue的基本操作

优先级队列(priority_queue)是一种特殊的队列，它按照元素的优先级进行排序，使得优先级最高的元素能够最先被取出。在C++中，标准库提供了priority_queue作为优先级队列的实现。下面我们将介绍priority_queue的基本操作。

#### 2.1 创建和初始化

在C++中，我们可以通过包含头文件`#include <queue>`来使用priority_queue。接下来，我们演示如何创建和初始化一个优先级队列。

#include <iostream>
#include <queue>
using namespace std;

int main() {
    // 创建一个最大堆的优先级队列
    priority_queue<int> max_pq;

    // 创建一个最小堆的优先级队列
    priority_queue<int, vector<int>, greater<int>> min_pq;

    // 初始化最大堆的优先级队列
    for (int i = 1; i <= 5; i++) {
        max_pq.push(i);
    }

    // 初始化最小堆的优先级队列
    for (int i = 1; i <= 5; i++) {
        min_pq.push(i);
    }

    return 0;
}

通过以上代码，我们展示了如何创建最大堆和最小堆的优先级队列，并对它们进行初始化。

#### 2.2 插入和删除元素

优先级队列提供了push和pop等操作来插入和删除元素，这些操作会根据优先级重新调整队列中的元素顺序。

// 插入元素
max_pq.push(10);

// 删除队首元素
max_pq.pop();

#### 2.3 获取队首元素和大小

我们可以使用top方法来获取队首元素，使用size方法来获取队列的大小。

// 获取最大堆的队首元素
int top_element = max_pq.top();

// 获取最大堆的大小
int size = max_pq.size();

在本节中，我们介绍了优先级队列的创建和初始化、插入和删除元素以及获取队首元素和大小的基本操作。在接下来的章节中，我们将深入探讨优先级队列的底层实现和应用场景。
### 3. 章节三：优先级队列的底层实现

#### 3.1 堆(heap)数据结构概述

在优先级队列的实现中，通常会使用堆（heap）这种数据结构。堆是一种完全二叉树，并且具有以下性质：

- 最大堆（Max Heap）：对于任意节点 i，它的值大于等于其父节点的值。
- 最小堆（Min Heap）：对于任意节点 i，它的值小于等于其父节点的值。

堆的底层实现可以使用数组来表示，利用数组的索引关系来表示节点之间的父子关系。

#### 3.2 堆的构建和调整

在使用堆实现优先级队列时，需要对堆进行构建和调整的操作。

- 构建堆（Heapify）：将一个无序的数组转化为一个堆，通过比较父节点和子节点的值，将较大（或较小）的值交换到父节点位置。
- 调整堆（Heapify Down）：在插入或删除元素后，需要对堆进行调整，使其仍然满足最大堆（或最小堆）的性质。

构建堆的过程可以分为自底向上和自顶向下两种方式，分别称为Bottom-Up Heap Construction和Top-Down Heap Construction。

#### 3.3 priority_queue的实现原理

priority_queue 是C++标准库中提供的一种优先级队列实现，底层使用的是最大堆（Max Heap）。在 priority_queue 中，每次插入一个元素时，会将元素放置在合适的位置，以保持最大堆的性质。同时，