给企业做网站多少钱,网站建设gxjzdrj,炫酷的企业网站,汕头网站模板价格文章目录 一、前言二、堆的基本概念1. 堆的定义2. 堆的存储方式 三、堆的基本操作1. 插入操作#xff08;Insert#xff09;C 实现#xff08;大根堆#xff09; 2. 删除堆顶元素#xff08;Extract Max / Min#xff09;C 实现#xff08;大根堆#xff09; 3. 堆排序… 文章目录 一、前言二、堆的基本概念1. 堆的定义2. 堆的存储方式 三、堆的基本操作1. 插入操作InsertC 实现大根堆 2. 删除堆顶元素Extract Max / MinC 实现大根堆 3. 堆排序Heap SortC 实现 五、堆的应用1. **优先队列**2. **求 Top K 问题**3. **Dijkstra 最短路径算法** 六、总结 一、前言
在数据结构中堆Heap是一种特殊的完全二叉树通常用于实现优先队列Priority Queue。堆分为大根堆Max Heap和小根堆Min Heap分别适用于不同的应用场景例如堆排序、求Top K问题、Dijkstra最短路径算法等。
本文将介绍堆的概念、基本操作、应用以及C和Python的代码实现。 二、堆的基本概念
1. 堆的定义
堆是一种完全二叉树并且满足以下性质
大根堆最大堆 父节点的值总是大于等于子节点的值。小根堆最小堆 父节点的值总是小于等于子节点的值。 完全二叉树如果树的每一层都被完全填满除了可能的最后一层并且最后一层的节点靠左对齐则称其为完全二叉树。 2. 堆的存储方式
堆通常用数组存储父子关系通过索引计算
父节点索引 parent(i) (i - 1) / 2左子节点索引 left(i) 2 * i 1右子节点索引 right(i) 2 * i 2 三、堆的基本操作
1. 插入操作Insert
插入新元素的步骤
将元素放入数组的末尾。进行上浮Heapify-Up操作调整堆结构。
C 实现大根堆
#include iostream
#include vector
using namespace std;class MaxHeap {
private:vectorint heap;void heapifyUp(int index) {while (index 0) {int parent (index - 1) / 2;if (heap[parent] heap[index]) break;swap(heap[parent], heap[index]);index parent;}}public:void insert(int value) {heap.push_back(value);heapifyUp(heap.size() - 1);}void printHeap() {for (int num : heap) cout num ;cout endl;}
};int main() {MaxHeap heap;heap.insert(10);heap.insert(20);heap.insert(5);heap.insert(30);heap.printHeap();return 0;
}输出示例
30 20 5 102. 删除堆顶元素Extract Max / Min
删除堆顶元素的步骤
将堆顶元素与堆的最后一个元素交换并移除最后一个元素。进行下沉Heapify-Down操作调整堆结构。
C 实现大根堆
void heapifyDown(int index) {int size heap.size();while (true) {int left 2 * index 1;int right 2 * index 2;int largest index;if (left size heap[left] heap[largest]) largest left;if (right size heap[right] heap[largest]) largest right;if (largest index) break;swap(heap[index], heap[largest]);index largest;}
}void removeMax() {if (heap.empty()) return;heap[0] heap.back();heap.pop_back();heapifyDown(0);
}3. 堆排序Heap Sort
堆排序的基本思想 建堆Heapify将无序数组转换为堆结构。 排序 交换堆顶元素与最后一个元素并移除最后一个元素。重新调整堆结构Heapify-Down。重复此过程直到所有元素有序。
C 实现
void heapSort(vectorint arr) {int n arr.size();// 构建最大堆for (int i n / 2 - 1; i 0; i--) {heapify(arr, n, i);}// 交换并调整堆for (int i n - 1; i 0; i--) {swap(arr[0], arr[i]);heapify(arr, i, 0);}
}五、堆的应用
1. 优先队列
堆可以高效地实现优先队列使得插入和取出最大最小值的时间复杂度为O(log N)。
2. 求 Top K 问题
使用大小为 K 的最小堆可以在 O(N log K) 的时间内求出前 K 大的元素。
import heapqdef topK(nums, k):return heapq.nlargest(k, nums) # 取前 K 个最大元素print(topK([3, 1, 5, 12, 2, 11], 3)) # [12, 11, 5]3. Dijkstra 最短路径算法
在图算法中堆被用于优化最短路径算法以高效找到当前最短路径的顶点。 六、总结
堆是完全二叉树常用于实现优先队列。堆的基本操作插入Heapify-Up、删除Heapify-Down、堆排序。堆的应用广泛包括 Top K 问题、Dijkstra 算法等。
堆的高效性使其在数据流处理、搜索优化、任务调度等场景下广泛使用是数据结构中非常重要的一部分。
