如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki<= K2*i+1 且 Ki<= K2*i+2(Ki >= K2*i+1 且 Ki >= K2*i+2) i = 0，1，2…，则称这个堆为最小堆(或最大堆)。 大堆：根节点的关键字大于其他所有节点的关键字它的左右子树也满足这个性质 小堆：根节点的关键字小于其他所有节点的关键字它的左右子树也满足这个性质
#pragma once #include <vector> #include <assert.h> #include <iostream> using namespace std; template<class T> //添加比较器 struct Less { bool operator()(const T& left, const T& right)//运用仿函数 { return left < right; } }; template<class T> struct Greater { bool operator()(const T& left, const T& ringht) { return left > ringht; } }; template<class T, class Compare = Less<T>> //默认创建小堆 class Heap { public: Heap() {} Heap(const T array[], size_t size) { CreateHeap(array, size); } void FindKBigNumber(const T arr[], size_t size, size_t k) { if (size <= k) { CreateHeap(arr, size); return; } CreateHeap(arr, k); size_t i = k; while (i < size) { if (_heap[0] < arr[i]) { _heap[0] = arr[i]; _AdjustDown(0); } i++; } } size_t Size()const { return _heap.size(); } T& Top() { assert(!_heap.empty()); return _heap[0]; } bool Empty()const { return _heap.empty(); } void Push(const T& data) { _heap.push_back(data); if (_heap.size() > 1 && Compare()(data, _heap[(_heap.size() - 2) >> 1])) { _AdjustUp(_heap.size() - 1); } } void Pop() { assert(!Empty()); size_t size = _heap.size(); std::swap(_heap[0], _heap[size - 1]); _heap.pop_back(); _AdjustDown(0); } protected: void CreateHeap(const T array[], size_t size) { if (array != NULL && size != 0) { _heap.resize(size); for (size_t i = 0; i < size; ++i) { _heap[i] = array[i]; } int root = (size - 2) >> 1; for (; root >= 0; root--) { _AdjustDown(root); } } } void _AdjustDown(size_t parent) { size_t size = _heap.size(); while (size > 1 && parent <= (size - 2) >> 1) { size_t child = 2 * parent + 1; Compare com; if (child + 1 < size) { //if (_heap[child] < _heap[child + 1]) if (com(_heap[child + 1], _heap[child])) child++; } //if (_heap[parent] < _heap[child]) if (com(_heap[child], _heap[parent])) { std::swap(_heap[parent], _heap[child]); parent = child; } else return; } } void _AdjustUp(int child) { int parent = (child - 1) >> 1; while (parent >= 0) { std::swap(_heap[parent], _heap[child]); child = parent; parent = (child - 1) >> 1; if (parent >= 0 && Compare()(_heap[parent], _heap[child])) return; } } protected: std::vector<T> _heap; };