C++ 实现最大堆排序与最大优先队列-白红宇

C++ 实现最大堆排序与最大优先队列

阅读量：6992 次

发布时间：2019-06-27

本文共 3211 字，大约阅读时间需要 10 分钟。

我一向赞同一个理念: 用代码实现简单逻辑是不需要注释的, 因此我也就不写注释了, 直接上代码:

#include 
     
      #include 
      
       #include 
       
        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
        
          &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
         
            BuildMaxHeap (std::deque
          
            &ideq){ std::deque
           
             heap (ideq); for (int i = ideq.size () / 2 - 1; i > -1; --i) { MaxHeapify (heap, i); } return std::move (heap);}void HeapSort (std::deque
            
              &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
             
               &heap){ const int topValue = heap[0]; return std::move(topValue);}int HeapExtractMax (std::deque
              
                &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
               
                 &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
                
                  &heap, int key){ heap.push_back (std::move(std::numeric_limits
                 
                  ::min())); HeapIncreaseKey (heap, heap.size() - 1, std::move(key));}void Print (const std::deque
                  
                    &ideq){ for (const auto &elem : ideq) { std::cout << elem << " "; }}int main (){ std::ios::sync_with_stdio (false); std::deque
                   
                     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;}