- 浏览: 131463 次
- 性别:
- 来自: 成都
最新评论
-
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 1176这里面包含了所有常见的排序操作 1.性能等比较分析 2 ... -
常见字符串操作大全
2012-08-12 11:34 14601.常见的字符串操作 如计算长度,求子串等都是考验基本功的, ... -
KMP算法解析
2012-08-12 11:35 2835一.理论基础 1.什么 ... -
set和map的简单实现
2012-08-10 11:35 13161.Set的简单实现 set是利用二叉查找树来实现的,而且为 ... -
红黑树的插入总结
2012-08-10 11:25 14051.红黑树 这个在july的博客中有详尽的说明,我就不在赘述 ... -
B-树实现
2012-08-10 11:03 16241.什么是B-树? 这个在我的前一篇博客中已经详细的阐释过: ... -
平衡二叉树
2012-08-10 10:39 28481.问题描述 什么是平衡 ... -
二叉排序树
2012-08-10 10:25 14751.基本概念 二叉排 ... -
B-树
2012-07-04 22:48 56661.B-树的概念 是一种多 ... -
构造哈夫曼树
2012-07-04 10:40 12301.算法说明 就是建造哈夫曼树树,从而使得构造出的树带权路径 ... -
线索二叉树
2012-07-04 09:20 12731.算法描述 就是简单的线索二叉树的建立,遍历,查找等基本操 ... -
二叉树基本操作大全
2012-07-03 18:22 26031.二叉树的基本操作 这里我有一个疑问: 在使用构造 ... -
多种队列的实现
2012-06-29 10:09 15511.算法描述 a.数据结构与算法(Mark Allen We ... -
栈的各种实现
2012-06-28 16:34 11091.算法描述 a.实现二个栈,在一个数组里面,除非没有任何空 ... -
中缀表达式转换为后缀
2012-06-28 11:10 18251.算法描述 例如a+b*c这是常见的中缀表达式,但是 ... -
后缀表达式的值
2012-06-27 16:33 13321.算法描述 计算后缀表达式的值 2.事例 如:( ... -
Josephus问题
2012-06-21 15:30 9961.算法描述 简单的游戏:有N个人坐成一圈,编号1-N、从编 ... -
关于最长递增子序列的实际应用--动态规划
2012-06-07 11:35 1830参考链接: a.http://www.programfan. ... -
线性查找二维数组
2012-06-05 17:23 10301.算法描述 有序(行有序,列有序,且每行从左至右递增 ... -
整数的随机置换
2012-06-05 15:10 2318算法描述:生成前N个整 ...
相关推荐
二叉堆实现A*寻路算法是计算机科学中一种经典的路径搜索方法,它结合了Dijkstra算法和优先级队列的特性,以高效的方式寻找从起点到目标点的最短路径。在这个C语言实例中,我们看到AStar.c、AStar.h、main.c和...
在给定的压缩包文件"C++二叉堆实现.zip"中,包含了两个文件:MyBinaryHeapTest.cpp 和 MyBinaryHeap.h。这表明这是一个C++项目,其中MyBinaryHeap.h文件可能定义了二叉堆类的接口,而MyBinaryHeapTest.cpp则实现了这...
4. 堆排序:堆排序是利用二叉堆实现的一种原地排序算法,通过构建最大堆或最小堆,然后不断交换堆顶元素与末尾元素,缩小堆的大小,直至堆只剩下一个元素。 四、C#中的二叉堆库 .NET框架虽然没有内置二叉堆类,但...
- Java的`PriorityQueue`类实现了`Queue`接口,它底层就是用二叉堆实现的。这个类不支持并集操作,但提供了`offer()`(插入)、`poll()`(删除并返回最小/最大元素)、`peek()`(查看但不移除最小/最大元素)等方法...
个人实现的最小权重的二叉堆实现,效率很高,适合任意场合下的临时列表排序。 直接执行该文件会执行文件中的测试样例 使用时在头部如此声明 from binaryheap import BinaryHeap bh = BinaryHeap(heap_size) # heap_...
1. 初始化:创建一个空的开放列表(通常使用二叉堆实现)和一个封闭列表。 2. 将起始节点加入开放列表,设置其G值(实际代价)为0,H值(启发式代价)根据预估路径计算,F值(总代价)为G + H。 3. 当开放列表非空时...
1. **二叉堆实现**:代码可能包含自定义的二叉堆类或使用了C++11的`std::priority_queue`。 2. **节点表示**:每个节点可能包含位置信息、代价(g值和h值)、父节点等信息,用于路径追踪和优先级计算。 3. **启发式...
在压缩包“二叉堆的相关代码.zip”中,包含了二叉堆实现的源代码。这些代码可能包括了二叉堆的初始化、插入元素、删除元素、构建堆、堆排序等功能的实现。通过学习和分析这些代码,你可以深入理解二叉堆的内部工作...
个人实现的最小权重的二叉堆实现,效率很高,适合任意场合下的临时列表排序。 可在外部写脚本对该文件进行测试 需要继承Tuple类实现排序对象类型,并实现Tuple的抽象方法weight()来反映排序对象权重
由两部分组成,my_map.cpp用OpenCV实现读取地图等图像处理操作,main.cpp实现A*算法。二叉堆为类,格子为结构体。生成结果后进行优化,使原本只能走8个方向的结果优化为任意角度和方向,也就是真正的全局最短路径。
二叉堆是一种特殊的数据结构,常用于实现优先队列或者优化某些算法。本篇将重点讨论PHP如何实现二叉堆及其主要操作,包括插入元素、删除元素等。 二叉堆通常分为两种类型:最大堆和最小堆。最大堆中每个节点的值都...
二叉堆、二项堆和斐波那契堆是数据结构中的重要概念,它们都是堆数据结构的不同变体,主要用于高效地实现某些特定操作,如查找最大或最小元素、优先队列以及各种排序算法。在C++编程语言中,理解和实现这些堆结构...
本文将深入探讨二叉堆的概念、性质、实现以及其在实际应用中的运用。 二叉堆是一个完全二叉树,可以分为两种类型:最大堆和最小堆。在最大堆中,每个节点的值都大于或等于其子节点的值;在最小堆中,每个节点的值都...
在易语言中实现二叉堆,可以帮助我们高效地执行一些操作,如查找最大或最小元素、插入元素以及删除元素等。 首先,我们要理解二叉堆的两种基本类型:最大堆和最小堆。最大堆中,每个父节点的值都大于或等于其子节点...
c++实现的二叉堆,很好的编程规范,可以学到模板、inline函数、引用的实际应用。代码写的很简洁
dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告 dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告 dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告
二叉堆通常用数组来实现,如果父节点在数组中的位置是p,则其左孩子的索引是2p+1,右孩子的索引是2p+2。 在Top K问题中,通常使用最小堆来实现。假设我们要找出最大的Top K个数,可以构建一个大小为K的小顶堆。小...
戴克斯特拉算法(Dijkstra’s algorithm)是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法...
使用c++实现最小堆。提供常见操作,如堆化数组,插入,删除,堆排序,遍历堆。