`
hao3100590
  • 浏览: 131245 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

二叉堆的实现

阅读更多

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;
}
分享到:
评论

相关推荐

    二叉堆实现A*寻路算法c语言实例

    二叉堆实现A*寻路算法是计算机科学中一种经典的路径搜索方法,它结合了Dijkstra算法和优先级队列的特性,以高效的方式寻找从起点到目标点的最短路径。在这个C语言实例中,我们看到AStar.c、AStar.h、main.c和...

    C++二叉堆实现.zip

    在给定的压缩包文件"C++二叉堆实现.zip"中,包含了两个文件:MyBinaryHeapTest.cpp 和 MyBinaryHeap.h。这表明这是一个C++项目,其中MyBinaryHeap.h文件可能定义了二叉堆类的接口,而MyBinaryHeapTest.cpp则实现了这...

    C# 二叉堆

    4. 堆排序:堆排序是利用二叉堆实现的一种原地排序算法,通过构建最大堆或最小堆,然后不断交换堆顶元素与末尾元素,缩小堆的大小,直至堆只剩下一个元素。 四、C#中的二叉堆库 .NET框架虽然没有内置二叉堆类,但...

    java-二叉堆(堆)binaryHeap

    - Java的`PriorityQueue`类实现了`Queue`接口,它底层就是用二叉堆实现的。这个类不支持并集操作,但提供了`offer()`(插入)、`poll()`(删除并返回最小/最大元素)、`peek()`(查看但不移除最小/最大元素)等方法...

    二叉堆 最小堆 Python 实现

    个人实现的最小权重的二叉堆实现,效率很高,适合任意场合下的临时列表排序。 直接执行该文件会执行文件中的测试样例 使用时在头部如此声明 from binaryheap import BinaryHeap bh = BinaryHeap(heap_size) # heap_...

    基于二叉堆的AStar算法演示程序

    1. 初始化:创建一个空的开放列表(通常使用二叉堆实现)和一个封闭列表。 2. 将起始节点加入开放列表,设置其G值(实际代价)为0,H值(启发式代价)根据预估路径计算,F值(总代价)为G + H。 3. 当开放列表非空时...

    SuanFan.zip_A二叉堆_A星 二叉堆_C++_c++11 a星算法_二叉堆

    1. **二叉堆实现**:代码可能包含自定义的二叉堆类或使用了C++11的`std::priority_queue`。 2. **节点表示**:每个节点可能包含位置信息、代价(g值和h值)、父节点等信息,用于路径追踪和优先级计算。 3. **启发式...

    二叉堆的相关代码.zip二叉堆的学习与思考

    在压缩包“二叉堆的相关代码.zip”中,包含了二叉堆实现的源代码。这些代码可能包括了二叉堆的初始化、插入元素、删除元素、构建堆、堆排序等功能的实现。通过学习和分析这些代码,你可以深入理解二叉堆的内部工作...

    二叉堆最小堆的Java实现

    个人实现的最小权重的二叉堆实现,效率很高,适合任意场合下的临时列表排序。 可在外部写脚本对该文件进行测试 需要继承Tuple类实现排序对象类型,并实现Tuple的抽象方法weight()来反映排序对象权重

    C++二叉堆实现A*算法及方向优化

    由两部分组成,my_map.cpp用OpenCV实现读取地图等图像处理操作,main.cpp实现A*算法。二叉堆为类,格子为结构体。生成结果后进行优化,使原本只能走8个方向的结果优化为任意角度和方向,也就是真正的全局最短路径。

    php 的二叉堆操作

    二叉堆是一种特殊的数据结构,常用于实现优先队列或者优化某些算法。本篇将重点讨论PHP如何实现二叉堆及其主要操作,包括插入元素、删除元素等。 二叉堆通常分为两种类型:最大堆和最小堆。最大堆中每个节点的值都...

    二叉堆(最小堆)+二项堆+斐波那契堆

    二叉堆、二项堆和斐波那契堆是数据结构中的重要概念,它们都是堆数据结构的不同变体,主要用于高效地实现某些特定操作,如查找最大或最小元素、优先队列以及各种排序算法。在C++编程语言中,理解和实现这些堆结构...

    二叉堆代码

    本文将深入探讨二叉堆的概念、性质、实现以及其在实际应用中的运用。 二叉堆是一个完全二叉树,可以分为两种类型:最大堆和最小堆。在最大堆中,每个节点的值都大于或等于其子节点的值;在最小堆中,每个节点的值都...

    易语言二叉堆

    在易语言中实现二叉堆,可以帮助我们高效地执行一些操作,如查找最大或最小元素、插入元素以及删除元素等。 首先,我们要理解二叉堆的两种基本类型:最大堆和最小堆。最大堆中,每个父节点的值都大于或等于其子节点...

    二叉堆c++代码

    c++实现的二叉堆,很好的编程规范,可以学到模板、inline函数、引用的实际应用。代码写的很简洁

    dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告

    dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告 dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告 dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告

    PHP利用二叉堆实现TopK-算法的方法详解

    二叉堆通常用数组来实现,如果父节点在数组中的位置是p,则其左孩子的索引是2p+1,右孩子的索引是2p+2。 在Top K问题中,通常使用最小堆来实现。假设我们要找出最大的Top K个数,可以构建一个大小为K的小顶堆。小...

    堆优化的Dijkstra算法用PYTHON实现

    戴克斯特拉算法(Dijkstra’s algorithm)是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法...

    二叉堆:最小堆

    使用c++实现最小堆。提供常见操作,如堆化数组,插入,删除,堆排序,遍历堆。

Global site tag (gtag.js) - Google Analytics