- 浏览: 128658 次
- 性别:
- 来自: 成都
最新评论
-
yi_chao_jiang:
你好,多谢分享,问个问题,在上传数据的时候判断文件是否有上传记 ...
断点续传和下载原理分析 -
a41606709:
为什么我的tabhost显示不出来? 怎么设置在全部页面中让他 ...
TabActivity中的Tab标签详细设置 -
Zero颴:
大神篇,思路,配图都很清晰,perfect!
Android事件模型之interceptTouchEvnet ,onTouchEvent关系正解 -
QAZ503602501:
牛死人了!!!
B-树 -
mengsina:
很牛的文档。数学功底好啊
Android Matrix理论与应用详解
1.堆的概念
这里只需要注意两点:
a.堆的存储方式:就是顺序存储在数组中,在二叉树中表现为满二叉树
b.堆的用处:用于排序,查找最大最小都非常方便
2.堆的实现
heapexception.h
#ifndef HEAPEXCEPTION_H #define HEAPEXCEPTION_H class ArrayOverFlowException{ public: const char* what() const throw() { return "array over flow exception!\n"; } }; class ParametersErrorException{ public: const char* what() const throw() { return "input error parameters exception!\n"; } }; class UnderFlowException{ public: const char* what() const throw() { return "the size out of array exception(position <= 0)!\n"; } }; #endif
heap.h
//二叉堆,是一颗被完全填满的二叉树,完全二叉树,故而可以使用顺序存储在数组中 #ifndef HEAP_H #define HEAP_H template<class T> class BinaryHeap{ public: BinaryHeap( ); BinaryHeap( const T* items, const int size); ~BinaryHeap(); bool isEmpty() const; const T& findMin() const; void insert( const T x);//注意:插入过程中,如果满了,则要resize void deleteMin(); void deleteMin( T& minItem); void makeEmpty(); private: int currentSize;//the number of elements in heap int capacity; void resize(int capacity); T* array;//the heap array void buildHeap(); void percolateDown(int hole);//将结点下滤,即从顶至叶子的调整过程 }; #endif
heap.cpp
#include <iostream> #include "heap.h" #include "heapexception.h" using namespace std; template<class T> BinaryHeap<T>::BinaryHeap(){ capacity = 100; array = new T[capacity]; currentSize = 0; } template<class T> BinaryHeap<T>::BinaryHeap( const T* items, const int size){ if(size <= 0) throw ParametersErrorException(); currentSize = size; capacity = size+10; array = new T[capacity]; for(int i=0; i<size; i++){ //注意:这里是从1开始存储,主要是为了计算的方便,如1的左右孩子就是1*2,1*2+1,从0就不行 array[i+1] = items[i]; } buildHeap(); } template<class T> BinaryHeap<T>::~BinaryHeap(){ delete[] array; } template<class T> bool BinaryHeap<T>::isEmpty() const{ if(currentSize == 0) return true; return false; } template<class T> const T& BinaryHeap<T>::findMin() const{ if(currentSize == 0) throw UnderFlowException(); return array[1]; } template<class T> void BinaryHeap<T>::insert( const T x){//注意:插入过程中,如果满了,则要resize if(currentSize == capacity-1){ resize(capacity); } //在最后建立一个空的位置,如果满足条件则上浮 int hole = ++currentSize; for(; hole>1 && x < array[hole/2]; hole/=2){ array[hole] = array[hole/2]; } array[hole] = x; } template<class T> void BinaryHeap<T>::deleteMin(){ if(currentSize == 0) throw UnderFlowException(); //将当前最新的交换到最后,在进行一次下滤 array[1] = array[currentSize--]; percolateDown(1); } template<class T> void BinaryHeap<T>::deleteMin( T& minItem){ if(currentSize == 0) throw UnderFlowException(); minItem = array[1]; array[1] = array[currentSize--]; percolateDown(1); } template<class T> void BinaryHeap<T>::makeEmpty(){ currentSize = 0; } template<class T> void BinaryHeap<T>::buildHeap(){ cout<<"build heap\n"; //建堆的过程就是从低到顶的将结点下滤 for(int i=currentSize/2; i>0; i--){ percolateDown(i); } } //将结点下滤,即从顶至叶子的调整过程(小根堆) template<class T> void BinaryHeap<T>::percolateDown(int hole){ int child; T tmp = array[hole]; for(; hole*2 <= currentSize; hole = child){ child = hole*2; if(child != currentSize && array[child+1] < array[child]){//右子树 child++; } //如果当前比hole小,交换 if(array[child]<tmp){ array[hole] = array[child]; }else{ break; } } //hole是最后交换的位置 array[hole] = tmp; } template<class T> void BinaryHeap<T>::resize(int capacity){ T* t = array; capacity = currentSize*2 + 1; array = new T[capacity]; for(int i=0; i<currentSize; i++){ array[i+1] = t[i]; } delete t; }
main.cpp
#include <iostream> #include "heapexception.h" #include "heap.cpp" using namespace std; int main(){ int a[] = {59, 48, 75, 98, 86, 23, 37, 59}; try{ BinaryHeap<int> bh(a, 8); int min; cout<<"------------------------\n"; cout<<bh.isEmpty()<<endl; cout<<"min:"<<bh.findMin()<<endl; bh.deleteMin(min); cout<<"min:"<<bh.findMin()<<endl; cout<<"insert"<<endl; bh.insert(10); cout<<"min:"<<bh.findMin()<<endl; bh.makeEmpty(); bh.findMin(); }catch(ArrayOverFlowException e){ cout<<e.what()<<endl; }catch(ParametersErrorException e){ cout<<e.what()<<endl; }catch(UnderFlowException e){ cout<<e.what()<<endl; } return 0; }
发表评论
-
排序方法总结
2012-08-12 11:34 1131这里面包含了所有常见的排序操作 1.性能等比较分析 2 ... -
常见字符串操作大全
2012-08-12 11:34 14161.常见的字符串操作 如计算长度,求子串等都是考验基本功的, ... -
KMP算法解析
2012-08-12 11:35 2774一.理论基础 1.什么 ... -
set和map的简单实现
2012-08-10 11:35 12761.Set的简单实现 set是利用二叉查找树来实现的,而且为 ... -
红黑树的插入总结
2012-08-10 11:25 9071.红黑树 这个在july的博客中有详尽的说明,我就不在赘述 ... -
B-树实现
2012-08-10 11:03 15871.什么是B-树? 这个在我的前一篇博客中已经详细的阐释过: ... -
平衡二叉树
2012-08-10 10:39 27941.问题描述 什么是平衡 ... -
二叉排序树
2012-08-10 10:25 14161.基本概念 二叉排 ... -
B-树
2012-07-04 22:48 56101.B-树的概念 是一种多 ... -
构造哈夫曼树
2012-07-04 10:40 11871.算法说明 就是建造哈夫曼树树,从而使得构造出的树带权路径 ... -
线索二叉树
2012-07-04 09:20 12371.算法描述 就是简单的线索二叉树的建立,遍历,查找等基本操 ... -
二叉树基本操作大全
2012-07-03 18:22 25541.二叉树的基本操作 这里我有一个疑问: 在使用构造 ... -
多种队列的实现
2012-06-29 10:09 14921.算法描述 a.数据结构与算法(Mark Allen We ... -
栈的各种实现
2012-06-28 16:34 10731.算法描述 a.实现二个栈,在一个数组里面,除非没有任何空 ... -
中缀表达式转换为后缀
2012-06-28 11:10 17501.算法描述 例如a+b*c这是常见的中缀表达式,但是 ... -
后缀表达式的值
2012-06-27 16:33 12891.算法描述 计算后缀表达式的值 2.事例 如:( ... -
Josephus问题
2012-06-21 15:30 9531.算法描述 简单的游戏:有N个人坐成一圈,编号1-N、从编 ... -
关于最长递增子序列的实际应用--动态规划
2012-06-07 11:35 1788参考链接: a.http://www.programfan. ... -
线性查找二维数组
2012-06-05 17:23 9991.算法描述 有序(行有序,列有序,且每行从左至右递增 ... -
整数的随机置换
2012-06-05 15:10 2231算法描述:生成前N个整 ...
相关推荐
由两部分组成,my_map.cpp用OpenCV实现读取地图等图像处理操作,main.cpp实现A*算法。二叉堆为类,格子为结构体。生成结果后进行优化,使原本只能走8个方向的结果优化为任意角度和方向,也就是真正的全局最短路径。
C++实现二叉堆
个人实现的最小权重的二叉堆实现,效率很高,适合任意场合下的临时列表排序。 直接执行该文件会执行文件中的测试样例 使用时在头部如此声明 from binaryheap import BinaryHeap bh = BinaryHeap(heap_size) # heap_...
此代码包含多个文件,AStar.c、 AStar.h、main.c以及makefile相关文件,例子默认是在linux下编译实现,也可直接将三个代码文件移植到window开发平台下编译实现
个人实现的最小权重的二叉堆实现,效率很高,适合任意场合下的临时列表排序。 可在外部写脚本对该文件进行测试 需要继承Tuple类实现排序对象类型,并实现Tuple的抽象方法weight()来反映排序对象权重
c++实现的二叉堆,很好的编程规范,可以学到模板、inline函数、引用的实际应用。代码写的很简洁
二叉堆(最小堆)+二项堆+斐波那契堆 根基算法导论C++实现
主要给大家介绍了PHP利用二叉堆实现TopK-算法的方法,文中介绍的非常详细,对大家具有一定的参考学习价值,需要的朋友们下面跟着小编一起来学习学习吧。
dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告 dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告 dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告
戴克斯特拉算法(Dijkstra’s algorithm)是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法...
使用c++实现最小堆。提供常见操作,如堆化数组,插入,删除,堆排序,遍历堆。
4.binaryHeap 二叉堆 支持排序,父子之间只有一种大小关系。孩子大于父,或者小于父。 二叉堆不支持合并。 实现了各种增删查改算法。
使用C++实现了A星算法,使用二叉堆优化。仅供新手学习。
使用c++实现最大堆。提供常见操作,如插入、删除、堆化数组、堆排序、上下调整、向下调整。
二叉堆详解实现优先级队列.md
下面小编就为大家带来一篇python下实现二叉堆以及堆排序的示例。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
二叉堆的实现数据结构中如何使用,我任务主要是在操作系统中的任务优先级调度问题,当然也可以用于实现堆排序问题,比如找出数组中的第K个最小值问题,采用二叉堆能够快速的实现,今天我就采用C语言实现了一个简单的...
博客代码,详见 : http://blog.csdn.net/kannimad/article/details/48861177