二叉堆(也可作为简单的优先队列)的建立、增、删、自调整。
main.cpp:
#include <iostream> #include "BinaryHeap.h" using namespace std; int main() { BinaryHeap<int> bh(BinaryHeap<int>::HeapType::MINIMEM); auto il = { 5,1,7,4,8,9 }; bh.push(il.begin(), il.end()); bh.show(); cout << endl; cout << "Pop head: " << bh.head() << endl; bh.pop(); bh.show(); cout << endl; return 0; }
BinaryHeap.h:
#pragma once #ifndef __BINARYHEAP_H__ #define __BINARYHEAP_H__ template<typename _Ty> class BinaryHeap { public: enum class HeapType :bool { MINIMEM = 0, MAXIMEM }; public: BinaryHeap() = default; BinaryHeap(HeapType _heapType) { heapType = _heapType; } ~BinaryHeap() { delete[] heapArr; heapArr = nullptr; } bool empty() const { return size_n == 0; } size_t size() { return size_n; } template<typename _Iter> void push(_Iter, _Iter); void push(const _Ty&); void pop(); void swap(); _Ty& head() 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 = 0; size_t MaxSize = 0; _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 = 10; heapArr = new _Ty[MaxSize]; } else if (MaxSize - size_n < 0) { MaxSize << 2; _Ty* tempArr = new _Ty[MaxSize]; for (size_t it = 0; it < size_n - 1; ++it) tempArr[it] = heapArr[it]; delete[] heapArr; heapArr = tempArr; tempArr = nullptr; } heapArr[size_n - 1] = _val; size_t childInex = size_n - 1; while (childInex > 0) { if (compare(_val, heapArr[(childInex - 1) / 2])) { heapArr[childInex] = heapArr[(childInex - 1) / 2]; childInex = (childInex - 1) / 2; } else break; } heapArr[childInex] = _val; } template<typename _Ty> void BinaryHeap<_Ty>::pop() { if (size_n == 0) return; --size_n; heapArr[0] = heapArr[size_n]; size_t childInex = 1; _Ty temp = heapArr[0]; while (childInex < size_n) { if (childInex + 1 < size_n && compare(heapArr[childInex + 1], heapArr[childInex])) ++childInex; if (compare(temp, heapArr[childInex])) break; heapArr[(childInex - 1) / 2] = heapArr[childInex]; childInex = 2 * childInex + 1; } heapArr[(childInex - 1) / 2] = temp; } template<typename _Ty> void BinaryHeap<_Ty>::swap() { std::swap(size_n); std::swap(MaxSize); std::swap(heapArr); std::swap(heapType); } template<typename _Ty> _Ty& BinaryHeap<_Ty>::head() const { if (heapArr == nullptr || size_n < 1) throw std::exception("Heap is empty."); return heapArr[0]; } template<typename _Ty> void BinaryHeap<_Ty>::show() const { for (size_t i = 0; 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__