二叉堆(1)BinaryHeap
2024-10-08 09:33:41
封装一个简单二叉堆,亦可视为优先队列。
测试文件 main.cpp:
#include <iostream> #include "BinaryHeap.h" using std::cout; using std::endl; int main() { BinaryHeap<int> bh(BinaryHeap<int>::HeapType::MINIMEM); auto il = { ,,,,, }; bh.push(il.begin(), il.end()); cout << "Elements:\n\t"; bh.show(); cout << endl << endl; cout << "Pop head: " << bh.top() << endl << endl; bh.pop(); cout << "Elements:\n\t"; bh.show(); cout << endl << endl; try { cout << ] << endl; cout << "bh[5]: "; cout << bh[] << endl; } catch (std::exception & e) { cout << e.what() << endl; } ; }
头文件 "BinaryHeap.h":
#pragma once #ifndef __BINARYHEAP_H__ #define __BINARYHEAP_H__ template<typename _Ty> class BinaryHeap { public: , MAXIMEM }; public: BinaryHeap() = default; BinaryHeap(HeapType _heapType) { heapType = _heapType; } ~BinaryHeap() { delete[] heapArr; heapArr = nullptr; } ; } size_t size() { return size_n; } template<typename _Iter> void push(_Iter, _Iter); void push(const _Ty&); void pop(); _Ty& top() const; void show() const; _Ty& operator [] (int); private: bool compare(const _Ty& _a, const _Ty& _b) { return (heapType == HeapType::MAXIMEM) ? (_a > _b) : (_a < _b); } private: size_t size_n = ; size_t MaxSize = ; _Ty* heapArr = nullptr; HeapType heapType = HeapType::MAXIMEM; }; template<typename _Ty> template<typename _Iter> void BinaryHeap<_Ty>::push(_Iter _it1, _Iter _it2) { while (_it1 != _it2) { push(*_it1); ++_it1; } } template<typename _Ty> void BinaryHeap<_Ty>::push(const _Ty& _val) { ++size_n; if (heapArr == nullptr) { MaxSize = ; heapArr = new _Ty[MaxSize]; } ) { MaxSize << ; _Ty* tempArr = new _Ty[MaxSize]; ; it < size_n - ; ++it) tempArr[it] = heapArr[it]; delete[] heapArr; heapArr = tempArr; tempArr = nullptr; } heapArr[size_n - ] = _val; size_t childInex = size_n - ; ) { ) / ])) { heapArr[childInex] = heapArr[(childInex - ) / ]; childInex = (childInex - ) / ; } else break; } heapArr[childInex] = _val; } template<typename _Ty> void BinaryHeap<_Ty>::pop() { ) return; --size_n; heapArr[] = heapArr[size_n]; size_t childInex = ; _Ty temp = heapArr[]; while (childInex < size_n) { < size_n && compare(heapArr[childInex + ], heapArr[childInex])) ++childInex; if (compare(temp, heapArr[childInex])) break; heapArr[(childInex - ) / ] = heapArr[childInex]; childInex = * childInex + ; } heapArr[(childInex - ) / ] = temp; } template<typename _Ty> _Ty& BinaryHeap<_Ty>::top() const { ) throw std::exception("Heap is empty."); ]; } template<typename _Ty> void BinaryHeap<_Ty>::show() const { ; i < size_n; ++i) std::cout << heapArr[i] << " "; } template<typename _Ty> _Ty& BinaryHeap<_Ty>::operator [] (int _index) { if (_index >= size_n) throw std::exception("Index out of range."); return heapArr[_index]; } #endif // !__BINARYHEAP_H__
最新文章
- iOS dealloc 不被调用的问题
- innodb buffer pool相关特性
- 蜕变&#183;WebRebuild 2013 前端年度交流会邀请
- 【转】C语言中标识符的作用域、命名空间、链接属性、生命周期、存储类型
- 更改printk打印级别
- poj 2251 Dungeon Master( bfs )
- jQuery中模拟用户操作
- windows8一直更新不了的问题————解决方案
- linux shell 终端中文乱码(转)
- QString::toLocal8Bit得听QTextCodec::codecForLocale的
- STM32F407的串口采用DMA收发数据
- 转:selenium webdriver 执行javascript代码
- App 监控、推广
- unity android相互调用
- char数据类型,编程能用的最小数据类型.
- C#关键字var是什么,在何种情况下使用
- Android SwipeMenuListView
- intrinsicConditionQueue笔记
- http://www.tangible-engineering.com/tangible_t4editor.html
- Linux的系统安全设置Shell脚本