大根堆和小根堆的介绍

堆（Heap）的基本概念

堆是一种完全二叉树（Complete Binary Tree），其性质使得堆可以高效地支持以下操作：

• 插入（Insert）：将一个新元素加入到堆中。
  
• 删除最大/最小元素（Delete Max/Min）：移除并返回堆中的最大（大根堆）或最小（小根堆）元素。
  
• 获取最大/最小元素（Get Max/Min）：返回堆中的最大（大根堆）或最小（小根堆）元素。
  

大根堆（Max-Heap）

特性：

• 每个节点的值都大于或等于其子节点的值。
  
• 根节点是堆中最大的元素。
  

插入操作：

• 将新元素插入到树的最底层的最后位置（保持完全二叉树的性质）。
  
• 进行“上浮”操作，将新元素逐步与其父节点交换，直到堆的性质恢复或到达根节点为止。
  

删除最大元素：

• 移除根节点。
  
• 将最后一个元素移动到根位置。
  
• 进行“下沉”操作，将根节点逐步与其较大的子节点交换，直到堆的性质恢复或到达叶子节点为止。
  

小根堆（Min-Heap）

特性：

• 每个节点的值都小于或等于其子节点的值。
  
• 根节点是堆中最小的元素。
  

插入操作：

• 将新元素插入到树的最底层的最后位置（保持完全二叉树的性质）。
  
• 进行“上浮”操作，将新元素逐步与其父节点交换，直到堆的性质恢复或到达根节点为止。
  

删除最小元素：

• 移除根节点。
  
• 将最后一个元素移动到根位置。
  
• 进行“下沉”操作，将根节点逐步与其较小的子节点交换，直到堆的性质恢复或到达叶子节点为止。
  

C++ 示例代码

以下是详细的 C++ 示例代码，展示如何实现大根堆和小根堆：
[code]#include //在c++中，使用优先队列需要包含queue这个头文件#include #include // 大根堆（默认行为）void maxHeapExample() {    // 创建一个大根堆    std::priority_queue maxHeap;    // 插入元素    maxHeap.push(10);    maxHeap.push(20);    maxHeap.push(5);    maxHeap.push(15);    std::cout