ToB企服应用市场:ToB评测及商务社交产业平台

标题: 大根堆和小根堆的介绍 [打印本页]

作者: 商道如狼道 时间: 2024-8-5 14:34
标题: 大根堆和小根堆的介绍
堆（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

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)