大根堆和小根堆的介绍
堆（Heap）的基本概念堆是一种完全二叉树（Complete Binary Tree），其性质使得堆可以高效地支持以下操作：
[*]插入（Insert）：将一个新元素加入到堆中。
[*]删除最大/最小元素（Delete Max/Min）：移除并返回堆中的最大（大根堆）或最小（小根堆）元素。
[*]获取最大/最小元素（Get Max/Min）：返回堆中的最大（大根堆）或最小（小根堆）元素。
大根堆（Max-Heap）
特性：
[*]每个节点的值都大于或等于其子节点的值。
[*]根节点是堆中最大的元素。
插入操作：
[*]将新元素插入到树的最底层的最后位置（保持完全二叉树的性质）。
[*]进行“上浮”操作，将新元素逐步与其父节点交换，直到堆的性质恢复或到达根节点为止。
删除最大元素：
[*]移除根节点。
[*]将最后一个元素移动到根位置。
[*]进行“下沉”操作，将根节点逐步与其较大的子节点交换，直到堆的性质恢复或到达叶子节点为止。
小根堆（Min-Heap）
特性：
[*]每个节点的值都小于或等于其子节点的值。
[*]根节点是堆中最小的元素。
插入操作：
[*]将新元素插入到树的最底层的最后位置（保持完全二叉树的性质）。
[*]进行“上浮”操作，将新元素逐步与其父节点交换，直到堆的性质恢复或到达根节点为止。
删除最小元素：
[*]移除根节点。
[*]将最后一个元素移动到根位置。
[*]进行“下沉”操作，将根节点逐步与其较小的子节点交换，直到堆的性质恢复或到达叶子节点为止。
C++ 示例代码
以下是详细的 C++ 示例代码，展示如何实现大根堆和小根堆：
#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
页:
[1]