首页 > 代码库 > C++ 实现最大堆排序与最大优先队列
C++ 实现最大堆排序与最大优先队列
我一向赞同一个理念: 用代码实现简单逻辑是不需要注释的, 因此我也就不写注释了, 直接上代码:
#include <iostream>#include <deque>#include <limits>inline int Parent (const int i){ return std::move( i % 2 ? (i - 1) / 2 : (i - 2) / 2);}inline int Left (const int i){ return std::move(2 * i + 1);}inline int Right (const int i){ return std::move(2 * i + 2);}void MaxHeapify (std::deque<int> &ideq, int node){ int largest = node; int limit = ideq.size (); auto SmallerThan = [&] (int child){ return (child < limit) && (ideq[largest] < ideq[child]); }; int leftNode = Left (node); if (SmallerThan (leftNode)) { largest = leftNode; } int rightNode = Right (node); if (SmallerThan (rightNode)) { largest = rightNode; } if (largest != node) { std::swap (ideq[largest], ideq[node]); MaxHeapify (ideq, largest); }}std::deque<int> BuildMaxHeap (std::deque<int> &ideq){ std::deque<int> heap (ideq); for (int i = ideq.size () / 2 - 1; i > -1; --i) { MaxHeapify (heap, i); } return std::move (heap);}void HeapSort (std::deque<int> &ideq){ auto heap = BuildMaxHeap (std::move(ideq)); for (int i = ideq.size () - 1; i > -1; --i) { ideq[i] = std::move (heap[0]); heap.pop_front (); MaxHeapify (heap, 0); }}int HeapMaximum (std::deque<int> &heap){ const int topValue = http://www.mamicode.com/heap[0]; return std::move(topValue);}int HeapExtractMax (std::deque<int> &heap){ if (heap.empty()) { std::cerr << "heap overfow!\n"; } int max = std::move(heap[0]); heap.pop_front (); MaxHeapify (heap, 0); return std::move (max);}void HeapIncreaseKey (std::deque<int> &heap, int &&node, int &&key){ if (key < heap[node]) { std::cerr << "This key is smaller than current key!\n"; } heap[node] = key; int parentNode = 0; while (( node > 0) && (parentNode = Parent(node), heap[parentNode] < key)){ std::swap (heap[parentNode], heap[node]); node = parentNode; }}void MaxHeapInsert (std::deque<int> &heap, int key){ heap.push_back (std::move(std::numeric_limits<int>::min())); HeapIncreaseKey (heap, heap.size() - 1, std::move(key));}void Print (const std::deque<int> &ideq){ for (const auto &elem : ideq) { std::cout << elem << " "; }}int main (){ std::ios::sync_with_stdio (false); std::deque<int> ideq{ 5, 13, 2, 25, 7, 17, 20, 9, 4}; auto maxHeap = BuildMaxHeap (ideq); HeapIncreaseKey (maxHeap, 0, 30); HeapIncreaseKey (maxHeap, maxHeap.size() - 1, 40); MaxHeapInsert (maxHeap, 35); Print (maxHeap); std::cout << std::endl; return 0;}
当然还有许多需要改进的地方, 还希望看官多提意见哈~
泛型的话还需要把 Less<_Ty>(_Ty lhs, _Ty rhs) 抽象出来, 甚至还有 Left<_Ty>(_Ty index), Right<_Ty>(_Ty index) 和 Parent<_Ty>(_Ty) 也要抽象出来. 只是这个博客的目的还是复习这个算法, 所以不作过多讨论.
当然要只是纯粹练习算法, 还是 python 更爽一些......
而且我不会说 STL 有个 priority_queue<type> 的......
C++ 实现最大堆排序与最大优先队列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。