网站建设评比文章,手机端网页界面设计,上海设计公司招聘,上海浦东网站建设公司堆是一种基于树结构的数据结构#xff0c;通常用于实现优先队列。堆分为最大堆和最小堆两种类型#xff0c;最大堆的每个节点的值都大于等于其子节点的值#xff0c;最小堆则相反#xff0c;每个节点的值都小于等于其子节点的值。
基础算法操作包括#xff1a;
1. 插入元…堆是一种基于树结构的数据结构通常用于实现优先队列。堆分为最大堆和最小堆两种类型最大堆的每个节点的值都大于等于其子节点的值最小堆则相反每个节点的值都小于等于其子节点的值。
基础算法操作包括
1. 插入元素将新元素插入堆的末尾然后通过上滤操作将其移到正确的位置。
2. 删除堆顶元素将堆顶元素与堆末尾元素交换然后将堆末尾元素删除最后通过下滤操作将堆顶元素移到正确的位置。
3. 上滤操作将一个新元素插入堆末尾后将其与其父节点比较如果大于等于父节点则不需要操作否则将其与父节点交换然后继续向上比较直到达到堆顶或者不需要交换为止。
4. 下滤操作将堆顶元素与其子节点比较如果小于等于子节点则不需要操作否则将其与子节点中较大或较小的那个交换然后继续向下比较直到达到堆底或者不需要交换为止。
5. 建堆操作将一个无序序列转化为堆的过程可以通过从最后一个非叶子节点开始进行下滤操作直到堆顶。
以下是基于数组实现的最小堆包括插入元素、删除堆顶元素、上滤操作、下滤操作和建堆操作的实现。
应用场景
堆是一种数据结构具有动态分配内存、动态扩容等特点在计算机科学中有许多应用场景。以下是堆的几个应用场景
1. 内存管理
堆常用于动态分配内存例如在程序运行时需要创建一个动态数组但是数组的大小在编译时是未知的这时可以使用堆来动态分配内存。C语言中的malloc和free函数就是堆的常见应用。
2. 优先队列
堆可以用来实现优先队列即队列中的元素按照某种优先级排序每次取出的元素是优先级最高的。堆实现优先队列的时间复杂度为O(logn)比其他实现方式的时间复杂度低因此在需要高效实现优先队列的场景中堆是一个常见的选择。
3. 排序算法
堆排序是一种高效的排序算法它的时间复杂度为O(nlogn)与快速排序、归并排序等常见的排序算法相当。堆排序的基本思路是将待排序的元素构建成一个二叉堆然后每次取出堆顶的元素将其放到已排序的序列中再对剩余的元素重新构建堆。
4. 图算法
在图算法中堆常用于实现Dijkstra算法和Prim算法。Dijkstra算法是一种求解单源最短路径问题的算法它通过维护一个距离起点最短的节点集合不断扩展该集合来求解最短路径。Prim算法是一种求解最小生成树问题的算法它通过维护一个已经生成的树的节点集合不断将与该集合相邻的未被访问的节点加入集合中直到生成一棵最小生成树。
5. 操作系统
堆在操作系统中也有广泛的应用例如进程管理中的内存分配和释放、虚拟内存管理中的页面置换等。在进程管理中堆用于动态分配进程的堆内存以及动态加载和卸载动态链接库。在虚拟内存管理中堆可以用于实现页面置换算法中的优先队列以便快速选择需要置换的页面。
c
#include iostream
#include vectorusing namespace std;class MinHeap {
private:vectorint heap; // 存储堆的数组// 上滤操作void siftUp(int index) {while (index 0) {int parent (index - 1) / 2;if (heap[parent] heap[index]) {swap(heap[parent], heap[index]);index parent;} else {break;}}}// 下滤操作void siftDown(int index) {int size heap.size();while (index * 2 1 size) {int leftChild index * 2 1;int rightChild index * 2 2;int minIndex leftChild;if (rightChild size heap[rightChild] heap[leftChild]) {minIndex rightChild;}if (heap[minIndex] heap[index]) {swap(heap[minIndex], heap[index]);index minIndex;} else {break;}}}public:// 插入元素void insert(int val) {heap.push_back(val);siftUp(heap.size() - 1);}// 删除堆顶元素void deleteMin() {int size heap.size();if (size 0) {return;}heap[0] heap[size - 1];heap.pop_back();siftDown(0);}// 建堆操作void buildHeap(vectorint nums) {heap nums;int size heap.size();for (int i size / 2 - 1; i 0; i--) {siftDown(i);}}// 获取堆顶元素int getMin() {return heap.size() 0 ? -1 : heap[0];}// 获取堆的大小int size() {return heap.size();}// 判断堆是否为空bool empty() {return heap.empty();}
};int main() {MinHeap heap;heap.insert(3);heap.insert(2);heap.insert(1);cout heap.getMin() endl; // 1heap.deleteMin();cout heap.getMin() endl; // 2heap.insert(0);cout heap.getMin() endl; // 0vectorint nums {5, 4, 3, 2, 1};heap.buildHeap(nums);while (!heap.empty()) {cout heap.getMin() ;heap.deleteMin();} // 1 2 3 4 5return 0;
}
