堆（Heap）的原理与C++实现

ops/2025/2/7 12:05:07/

1. 什么是堆？

堆（Heap）是一种特殊的树形数据结构，通常用于实现优先队列。堆可以分为两种类型：

  • 最大堆（Max Heap）：每个节点的值都大于或等于其子节点的值。
  • 最小堆（Min Heap）：每个节点的值都小于或等于其子节点的值。

堆通常是一个完全二叉树，这意味着除了最后一层，其他层都是完全填满的，并且最后一层的节点都尽可能地靠左排列。

2. 堆的性质

  • 完全二叉树：堆是一个完全二叉树，这意味着它可以用数组来高效地表示。
  • 堆序性质：在最大堆中，父节点的值总是大于或等于其子节点的值；在最小堆中，父节点的值总是小于或等于其子节点的值。

Tips: 堆是完全二叉树，并非二叉搜索树

在数据结构中，完全二叉树和二叉搜索树是两种常见的树形结构，它们虽然都属于二叉树的范畴，但在定义、性质和应用场景上有显著的区别。下面我们将详细分析它们的区别。

特性完全二叉树二叉搜索树
定义节点从上到下、从左到右依次填充左子树 < 根节点 < 右子树
有序性不一定有序中序遍历结果有序
结构要求必须是完全填充的（最后一层靠左）无特殊结构要求，只需满足有序性
查找效率不支持高效查找支持高效查找（平衡时 O(log n)）
插入和删除通常用于堆操作，不支持动态插入删除支持动态插入和删除
应用场景堆、优先队列查找、排序、数据库索引
数组表示可以用数组高效表示通常用指针或引用表示

完全二叉树示例

        10/  \5    15/ \   /2   7 12
  • 节点从上到下、从左到右依次填充。
  • 最后一层的节点靠左排列。

二叉搜索树示例

        10/  \5    15/ \   / \2   7 12 20
  • 左子树的所有节点值小于根节点，右子树的所有节点值大于根节点。
  • 中序遍历结果为 [2, 5, 7, 10, 12, 15, 20]，是一个有序序列。

3. 堆的操作

堆的主要操作包括：

  • 插入（Insert）：将一个新元素插入堆中，并保持堆的性质。
  • 删除（Delete）：删除元素，并保持堆的性质。
  • 查询（Query）：查询堆顶元素
  • 构建堆（Build Heap）：将一个无序数组构建成一个堆。

4. 堆的实现

堆通常使用数组来实现。在从数组下标0开始存储的堆，对于一个索引为 i 的节点：

  • 其父节点的索引为 (i - 1) / 2
  • 其左子节点的索引为 2 * i + 1
  • 其右子节点的索引为 2 * i + 2

4.1 堆的性质维护

堆的插入过程

假设我们有一个最大堆，初始堆为：[100, 19, 36, 17, 3, 25, 1, 2, 7]，其对应的完全二叉树结构如下（用数组表示）：

        100/     \19       36/  \     /  \17   3   25   1/ \
2  7

插入一个新元素40
将新元素添加到堆的末尾：堆的数组表示为 [100, 19, 36, 17, 3, 25, 1, 2, 7, 40]，对应的完全二叉树结构如下：

     100/      \19      36/   \    / \17    3  25  1
/ \    /
2  7  40
  1. 向上调整（上浮）：从新插入的节点开始，与其父节点比较。如果当前节点的值大于父节点的值，则交换它们的位置。
  • 40 的父节点是 3，40 > 3，交换它们的位置：
        100/      \19       36/  \     /  \17   40  25   1/ \   /2  7  3
  • 40 的新父节点是 19，40 > 19，交换它们的位置：
      100/      \40       36/  \     /  \
17   19  25   1
/ \   /
2  7 3
  • 40 的新父节点是 100，40 < 100，停止调整。
  • 最终，插入 40 后的堆为：[100, 40, 36, 17, 19, 25, 1, 2, 7, 3]。

总结:堆在插入元素后，需要进行上浮（up）操作，是不断与父节点比较，若父节点小于当前节点，则交换位置。具体代码实现示例如下：

//存储下标从1开始，以大根堆为例
void heap_up(int idx){while(idx != 1){int parent = idx >> 1;if(heap[parent] < heap[idx]){swap(heap[parent], heap[idx]);idx = parent;}else{break;}}
}
堆的删除过程

假设我们从上述堆中删除最大值（堆顶元素 100）。

  1. 将堆顶元素与最后一个元素交换：交换 100 和 3 的位置，得到 [3, 40, 36, 17, 19, 25, 1, 2, 7, 100]，然后删除最后一个元素（100），得到 [3, 40, 36, 17, 19, 25, 1, 2, 7]。这是因为我们在用数组存储堆的时候，头部元素的删除面临整个数组的移动，相当消耗计算资源，于是我们选择将头部元素和尾部元素进行交换，进行删除尾部，再调整堆
  2. 向下调整（下沉）：从堆顶开始，比较当前节点与其子节点的值，将当前节点与较大的子节点交换，直到满足堆的性质。
  • 当前堆顶是 3，其子节点是 40 和 36，40 > 36，选择 40 与 3 交换得到：
      40/      \3       36/  \     /  \
17   19  25   1
/ \  
2  7
  • 3 的新位置是左子树的根，其子节点是 17 和 19，19 > 17，选择 19 与 3 交换：
      40/      \19       36/  \     /  \
17   3  25   1
/ \  
2  7
  • 最终，删除 100 后的堆为：[40, 19, 36, 17, 3, 25, 1, 2, 7]。
void heap_down(int idx){int size = top;while(1){int leftChild = idx * 2;int rightChild = idx * 2 + 1;int largest = idx;if(leftChild < size && heap[largest] < heap[leftChild]){largest = leftChild;}if(rightChild < size && heap[largest] < heap[rightChild]){largest = rightChild;}if (largest != idx) {swap(heap[idx], heap[largest]);idx = largest;} else {break;}}
}

4.2 C++ 实现最大堆

这里展示一个封装成对象的大根堆

#include <iostream>
#include <vector>
#include <algorithm>class MaxHeap {
private:std::vector<int> heap;void heapifyUp(int index) {while (index > 0) {int parentIndex = (index - 1) / 2;if (heap[index] > heap[parentIndex]) {std::swap(heap[index], heap[parentIndex]);index = parentIndex;} else {break;}}}void heapifyDown(int index) {int size = heap.size();while (true) {int leftChild = 2 * index + 1;int rightChild = 2 * index + 2;int largest = index;if (leftChild < size && heap[leftChild] > heap[largest]) {largest = leftChild;}if (rightChild < size && heap[rightChild] > heap[largest]) {largest = rightChild;}if (largest != index) {std::swap(heap[index], heap[largest]);index = largest;} else {break;}}}public:void insert(int value) {heap.push_back(value);heapifyUp(heap.size() - 1);}int extractMax() {if (heap.empty()) {throw std::out_of_range("Heap is empty");}int maxValue = heap[0];heap[0] = heap.back();heap.pop_back();heapifyDown(0);return maxValue;}void buildHeap(const std::vector<int>& array) {heap = array;for (int i = (heap.size() / 2) - 1; i >= 0; --i) {heapifyDown(i);}}void printHeap() const {for (int value : heap) {std::cout << value << " ";}std::cout << std::endl;}
};int main() {MaxHeap maxHeap;maxHeap.insert(10);maxHeap.insert(20);maxHeap.insert(15);maxHeap.insert(30);maxHeap.insert(40);std::cout << "Max Heap: ";maxHeap.printHeap();std::cout << "Extracted Max: " << maxHeap.extractMax() << std::endl;std::cout << "Max Heap after extraction: ";maxHeap.printHeap();std::vector<int> array = {5, 3, 8, 1, 9};maxHeap.buildHeap(array);std::cout << "Max Heap built from array: ";maxHeap.printHeap();return 0;
}

4.2 代码解析

  • heapifyUp：用于在插入新元素后，从下往上调整堆，确保堆的性质。
  • heapifyDown：用于在删除堆顶元素后，从上往下调整堆，确保堆的性质。
  • insert：将新元素插入堆中，并调用 heapifyUp 进行调整。
  • extractMax：删除并返回堆顶元素，然后调用 heapifyDown 进行调整。
  • buildHeap：将一个无序数组构建成一个堆。

5. 堆的应用

  • 优先队列：堆是实现优先队列的理想数据结构，因为可以快速获取和删除最大或最小元素。
  • 堆排序：堆排序是一种基于堆的比较排序算法，时间复杂度为 O(n log n)。
  • Dijkstra算法：在图的单源最短路径算法中，堆用于高效地选择下一个要处理的节点。

6. 总结

堆是一种非常高效的数据结构，特别适用于需要频繁获取最大或最小元素的场景。通过数组实现堆，可以充分利用其完全二叉树的性质，使得插入、删除和构建堆的操作都能在 O(log n) 的时间内完成。

7.练习

ACWing模拟堆
这个题相较普通的堆，增添了一个需要维护的对象，就是这个数字是第几次插入的。所以我们需要额外维护两个数组pos和inv_pos，分别表示第k个插入的数在堆数组中的索引，和堆数组中第i个数是第几个插入的，完整代码如下：

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
const int maxn = 1e5 + 7;
int heap[maxn], top;
int pos[maxn], inv_pos[maxn];
void heap_swap(int a, int b){swap(heap[a], heap[b]);swap(pos[inv_pos[a]], pos[inv_pos[b]]);swap(inv_pos[a], inv_pos[b]);
}
void down(int idx){while(1){int leftChild = idx * 2;int rightChild = idx * 2 + 1;int smallest = idx;if(leftChild <= top && heap[leftChild] < heap[smallest])smallest = leftChild;if(rightChild <= top && heap[rightChild] < heap[smallest])smallest = rightChild;if(idx != smallest) {heap_swap(idx, smallest);idx = smallest;}elsebreak;}
}
void up(int idx){while(idx != 1){int parent = idx >> 1;if(heap[parent] > heap[idx]){heap_swap(idx, parent);idx = parent;}else{break;}}
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin>>n;string op;int x, k, cnt = 0;while(n--){cin>>op;if(op == "I"){cin>>x;heap[++top] = x;pos[++cnt] = top;inv_pos[top] = cnt;up(top);}else if(op == "PM"){cout<<heap[1]<<endl;}else if(op == "DM"){heap_swap(1, top);top--;down(1);}else if(op == "D"){cin>>k;int now = pos[k];heap_swap(now, top);top --;down(now);up(now);}else if(op == "C"){cin>>k>>x;heap[pos[k]] = x;up(pos[k]);down(pos[k]);}}return 0;
}

http://www.ppmy.cn/ops/156426.html

相关文章

被裁与人生的意义--春节随想

被裁与人生的意义--春节随想

还有两个月就要被迫离开工作了十多年的公司了&#xff0c;整个中国分支全部干掉。不过我有幸安安稳稳的过了一个春节&#xff0c;很知足! 分六七批走人&#xff0c;我是最后一批离开&#xff0c;一百多号同事都没“活到”蛇年。看着一批批仁人志士被“秋后斩首”&#xff0c;马…
阅读更多...
6.攻防世界 shrine

6.攻防世界 shrine

进入题目页面如下 是python代码 进行代码审计 # 从 flask 库中导入 Flask 类 from flask import Flask import os# 创建一个 Flask 应用实例 app Flask(__name__)# 从环境变量中获取名为 FLAG 的值&#xff0c;并将其设置为应用配置中的 FLAG 项&#xff0c;同时从环境变量中…
阅读更多...
基于WiFi的智能照明控制系统的设计与实现（论文+源码）

基于WiFi的智能照明控制系统的设计与实现（论文+源码）

1系统方案设计 本设计智能照明控制系统&#xff0c;结合STM32F103单片机、光照检测模块、显示模块、按键模块、太阳能板、LED灯模块、WIFI模块等器件构成整个系统&#xff0c;在功能上可以实现光照强度检测&#xff0c;并且在自动模式下可以自动调节照明亮度&#xff0c;在手动…
阅读更多...
前缀和算法详解：快速求解区间和的利器（含C++板子）

前缀和算法详解：快速求解区间和的利器（含C++板子）

前缀和算法详解&#xff1a;快速求解区间和的利器 引言 在算法和数据处理中&#xff0c;区间求和是常见的基础操作。传统暴力解法每次查询需要遍历区间元素&#xff0c;当面对海量查询时效率极低。本文将介绍一种名为前缀和的高效算法&#xff0c;它能将区间求和的时间复杂度…
阅读更多...
ASP.NET Core中Filter与Middleware的区别

ASP.NET Core中Filter与Middleware的区别

中间件是ASP.NET Core这个基础提供的功能&#xff0c;而Filter是ASP.NET Core MVC中提供的功能。ASP.NET Core MVC是由MVC中间件提供的框架&#xff0c;而Filter属于MVC中间件提供的功能。 区别 中间件可以处理所有的请求&#xff0c;而Filter只能处理对控制器的请求&#x…
阅读更多...
H3CIE-RS+面试——OSPF（倒计时第40天）

H3CIE-RS+面试——OSPF（倒计时第40天）

以下内容均为博主自己根据华三官网ppt整理的笔记，仅供参考，如有错误，轻喷 OSPF（开放最短路径优先） OSPF协议基本原理 ospf协议特点 基于链路状态的内部网关协议没有路由跳数的限制采用组播通告邻居路由发生变化 组播地址224.0.0.5，所有运行了OSPF的路由器都会监听该地址…
阅读更多...
构建高效Facebook广告矩阵：精准营销与广告投放的全新策略

构建高效Facebook广告矩阵：精准营销与广告投放的全新策略

随着社交媒体广告成为企业营销不可或缺的一部分&#xff0c;Facebook作为全球最大的社交平台之一&#xff0c;已成为企业营销的重要阵地。在Facebook上成功的广告投放&#xff0c;往往不只是依赖于单一广告&#xff0c;而是通过构建一个精准的广告矩阵来提升品牌曝光、增强用户…
阅读更多...
前端学习-tab栏切换改造项目（三十一）

前端学习-tab栏切换改造项目（三十一）

目录 前言 监听代码 思路 代码 事件委托代码 思路 代码 总结 前言 星垂平野阔&#xff0c;月涌大江流 监听代码 思路 等待DOM加载完成 获取所有标签 为每个标签添加鼠标悬停事件监听器 定义showTab函数&#xff1a; 接收一个索引参数index&#xff0c;用于标识当前悬停…
阅读更多...
最新文章

Copyright @ 2022~2023