- 浏览: 723186 次
- 性别:
- 来自: 深圳
文章分类
- 全部博客 (1043)
- 数据结构 (36)
- UML与设计模式 (42)
- c++ (87)
- rust (36)
- Qt (41)
- boost模板元编程 (43)
- Linux (77)
- 汇编 (4)
- 其它 (2)
- 烹饪 (3)
- unix c / socket (73)
- 软件工程 (4)
- shell (52)
- Python (37)
- c++ primer 5th(c++11) (22)
- 数据库/MySQL (27)
- 数据存储 (4)
- lisp (7)
- git (4)
- Utility (3)
- CDN与DNS (54)
- Http (53)
- php (7)
- nginx/lua/openresty (41)
- redis (11)
- TCP/IP (16)
- 互联网 (6)
- kernel (2)
- go (34)
- 区块链 (43)
- 比特股 (13)
- 以太坊 (23)
- 比特币 (23)
- 密码学 (10)
- EOS (53)
- DAG (1)
- docker (1)
- filecoin (7)
- solidity (64)
- ipfs (8)
- 零知识证明 (1)
- openzeppelin (3)
- java (1)
- defi (7)
最新评论
在优先级队列的各种实现中,堆是最高效的一种数据结构
关键码:在各个数据记录中存在一个能够标识数据记录(或元素)的数据项,并将依据该数据项对数据进行组织,这个数据项就是关键码
最小堆:父结点总是小于等于子结点
最大堆:父结点总是大于等于子结点
MinHeap.h
MinHeap.cpp
关键码:在各个数据记录中存在一个能够标识数据记录(或元素)的数据项,并将依据该数据项对数据进行组织,这个数据项就是关键码
最小堆:父结点总是小于等于子结点
最大堆:父结点总是大于等于子结点
MinHeap.h
#ifndef MINHEAP_H #define MINHEAP_H #include"../T3/PQueue.h" #include<assert.h> #define DefaultSize 10 template<typename E> class MinHeap:public PQueue<E>{ public: MinHeap(int sz=DefaultSize); MinHeap(E arr[],int n); ~MinHeap(){delete[]heap;} bool Insert(const E &x); bool RemoveMin(E &x); bool IsEmpty() const{ return currentSize==0?true:false; } bool IsFull()const{ return currentSize==maxHeapSize?true:false; } void makeEmpty(){ currentSize=0; } void display(); private: E *heap; int currentSize; int maxHeapSize; void siftDown(int start,int m); void siftUp(int start); }; template<typename E> MinHeap<E>::MinHeap(int sz) { maxHeapSize=sz>DefaultSize?sz:DefaultSize; heap=new E[maxHeapSize]; assert(heap!=NULL); currentSize=0; } /* 最小堆的下滑高速算法 */ template<typename E> void MinHeap<E>::siftDown(int start, int m) { int i=start,j=2*i+1; E temp = heap[i]; while(j<=m){ if(j<m&&heap[j]>heap[j+1]){ j++;//指向子女中最小的一个 } if(temp<=heap[j]){ break; }else{ heap[i]=heap[j]; i=j; j=j*2+1; } } heap[i]=temp; } template<typename E> MinHeap<E>::MinHeap(E arr[], int n) { maxHeapSize=n>DefaultSize?n:DefaultSize; heap=new E[maxHeapSize]; assert(heap!=NULL); for(int i=0;i<n;++i) heap[i]=arr[i]; currentSize=n; int currentPos=(currentSize-2)/2; while(currentPos>=0){//自底向上逐步扩大 siftDown(currentPos,currentSize-1); currentPos--; } } /* 把start处的结点向上调整 */ template<typename E> void MinHeap<E>::siftUp(int start) { int j=start,i=(j-1)/2; E temp=heap[j]; while(j>0){ if(heap[i]<=temp){ break; }else{ heap[j]=heap[i]; j=i; i=(i-1)/2; } } heap[j]=temp; } template<typename E> bool MinHeap<E>::Insert(const E &x) { if(currentSize==maxHeapSize){ cerr << "full" << endl; return false; } heap[currentSize]=x; siftUp(currentSize); currentSize++; return true; } template<typename E> bool MinHeap<E>::RemoveMin(E &x) { if(currentSize==0){ cout << "empty" << endl; return false; } x=heap[0]; currentSize--; siftDown(0,maxHeapSize-1); return true; } template<typename E> void MinHeap<E>::display() { for(int i=0;i<currentSize;++i) cout << heap[i] << " "; } #endif // MINHEAP_H
MinHeap.cpp
#include "MinHeap.h" int main(){ int a[10]={53,17,78,9,45,65,87,23}; MinHeap<int> minHeap(a,8); minHeap.display(); } 9 17 65 23 45 78 87 53
发表评论
-
时间复杂度推导
2012-06-05 22:57 9121.用常数1取代运行时间中的所有加法常数 2.在修改后的运行次 ... -
数据结构概论2
2012-06-04 22:19 766数据元素:组成数据的,有一定意义的基本单位,在计算机中通常作为 ... -
排序概念
2011-06-24 14:51 755数据表:待排序数据元素的有很集合 排序码:通常数据元素有多个 ... -
图的基本概念
2011-06-20 16:18 726完全图:n个顶点,n*(n-1)/2个边的无向图,就是无向完全 ... -
红黑树
2011-06-16 14:29 480红黑树: 1.根结点和所有的叶结点都是黑色 2.从根结点到叶结 ... -
链表反转
2011-06-12 18:03 1062template<typename T> v ... -
散列表(哈希表)
2011-06-09 09:55 1023散列表(hash table):是表示集合和字典的另一种有效方 ... -
跳 表
2011-06-08 11:12 771#ifndef SKIPLIST_H #define S ... -
字 典
2011-06-08 10:06 887字典:以集合为基础,并支持支持Member,Insert和Re ... -
LinkedSet
2011-06-07 13:08 891改了很久的bug #ifndef LINKEDSET_H ... -
bitset
2011-06-06 12:27 849bitSet.h #ifndef BITSET_H #d ... -
Huffman树
2011-06-02 11:06 859Huffman树,又称最优二叉树,是一类加权路径长度最短的二叉 ... -
森 林
2011-06-01 11:09 560森林与二叉树互转,主要是子结点转左子树,兄弟结点转右子树 深 ... -
二叉树的链式实现
2011-05-31 11:24 1241binaryTree.h #ifndef LINKEDBI ... -
二叉树基本概念
2011-05-30 10:05 808一棵二叉树的结点的一个有限集合:该集合或者为空,或者是由一个根 ... -
树基本概念
2011-05-30 09:28 863结点(node):包含数据项及指向其他结点的分支。 结点的度( ... -
广义表
2011-05-27 10:57 896广义表的定义是递归的,因为在表的描述中又用到了表,允许表中有表 ... -
矩阵相关
2011-05-26 10:22 890矩阵:是一个具有m行n列的二维数组。 上三角矩阵:只存储对角 ... -
优先级队列
2011-05-21 11:24 575PQueue.h #ifndef PQUEUE_H #d ... -
链式队列
2011-05-20 12:05 802LinkedQueue.h #ifndef LINKEDQ ...
相关推荐
现要将石子有次序地合并成一堆, 规定每次只能选相邻的 2 堆石子合并成新的一堆, 并将新的一堆石子数记为该次合并的得分. 本题对于给定 n 堆石子, 计算合并成一堆的最小得分和最大得分. Input 测试用例的第 1 行...
最大堆最小堆 问题的提出 给定k个排好序的序列S1,S2…,Sk,用2路合并算法将这k个序列合并成一个序列。假设所采用的2路合并算法合并2个长度分别为m和n的序列需要m+n-1次比较。试设计一个算法确定合并这个序列的最优...
二叉堆(最小堆)+二项堆+斐波那契堆 根基算法导论C++实现
规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。 编程任务: 对于给定n堆石子,编程计算合并成一堆的最小...
为了研究快堆悬浮式非能动停堆组件结构对于移动体落棒性能的影响,指导结构设计,基于钠冷快堆(SFR)悬浮式非能动停堆机构组件移动体的水动力及运动学分析,设计开发了非能动停堆组件移动体落棒性能水动力学分析...
交换机堆叠教程文档,文档介绍交换机堆叠的实例和命令,为交换机堆叠提供参考案例。 交换机堆叠教程文档,文档介绍交换机堆叠的实例和命令,为交换机堆叠提供参考案例。 交换机堆叠教程文档,文档介绍交换机堆叠的...
上个资源的有效排序下标是由1开始的,0只做了填充作用,这次则由下标0为根节点: ... //交换堆的第一个元素和堆的最后一个元素 A[i] = A[0]; A[0] = temp; i--; //堆的大小减一 MaxHeapIfy(A, i, 0); //调堆 }
欢迎多多交流 ps:按照书中伪码写成,元素由1开始,故数组中第一位A[0]为填充,并不算... //交换堆的第一个元素和堆的最后一个元素 A[i] = A[1]; A[1] = temp; i--; //堆的大小减一 MaxHeapIfy(A, i, 1); //调堆 }
二维数据或者图片堆叠在三维空间的表示,图片堆叠方便查看 类似origin里面的瀑布图的方法,只是这是在matlab里面实现。 matlab多张图片同时在三维空间中显示,沿着某一个坐标轴 matlab在一个坐标系画不同三维图综合...
用函数实现堆排序,并输出每趟排序的结果 Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 第一行:初始建堆后的结果 其后各行输出交换堆顶元素并调整堆的结果,数据...
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。 堆排序的平均时间复杂度为Ο...
H3C华为交换机堆叠配置大全 作为网络管理员的我们都会面对配置交换机的工作,毕竟几乎所有中小企业都建立了自己的网络,连接各个计算机的最常见的设备就是交换机。因此维护交换机这样的工作就落到了网络管理员的身上...
由于煤炭生产环境较为恶劣,刮板输送机在前一部设备停运的状态下很容易使得机头堆满原煤,造成堵死,影响设备的正常生产甚至有可能损坏设备,造成人员伤亡等。因此,设计一种堆煤保护装置,对于保障刮板输送机的安全稳定...
数组堆的实现 堆的实现 c++实现 支持自定义值类型、自定义用于比较的函数对象
1、 实现堆排序算法。 2、 理论分析并实验验证堆排序算法的时间复杂度。
利用最小堆编程实现给定权值集合下构造相应霍夫曼树的算法,并解决以下问题: 有一电文共使用五种字符a,b,c,d,e,其出现频率依次为4,7,5,2,9。 (1)构造对应的编码哈夫曼树(要求左子树根结点的权小于等于右子树根结点...
华罗庚的经典著作《堆垒素数论》1953版的,阅读本书需要具备一定的数论基础知识,如初等数论,解析数论的一些基础,具体内容,第一章:三角和法,第二章:包含除数函数的和估计,第三,四章:某些三角和的中值定理,...
本人编写的堆排序及堆的插入删除等操作演示,用的是java swing,详情可以查看 http://blog.csdn.net/cdnight/article/details/11714005 假如您对堆排序不是很熟悉,可以查看 ...
C++ 内存池私有堆 实现 测试代码 私有堆管理类 1. CPrivateHeap: 自动创建和销毁进程私有堆 每一个该类的对象都代表一个私有堆, 所以该类对象的特点是: 一般声明周期都比较长 通常作为全局对象, 其他类的静态成员...