首页 > 代码库 > 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++ 实现最大堆排序与最大优先队列