前几天处理工作方面的事情, 确实耽误了几天, 导致博客停更了, 今天上午看到算法导论的堆排序, 想用 C++ 实现下, 就当练练手了.

算法导论里使用的是起始编号为 1 的容器, 那么实现的方法要不就是把 STL 容器打包, 自己建一个起始编号为 1 的容器, 要不就按照起始编号为 0 的来. 想了一下总觉得第一种方案有种削足适履的蛋疼感, 就是写出来也只能表示我对于 STL 容器的理解而不是对算法的理解, 因此如果真正理解了堆排序的思想, 那么无论是以什么值为起始编号都是一样的. 所以我选择了第二个方案, 代码如下:

#include 
     
      #include 
      
       inline int Left (int i){    return 2 * i + 1;}inline int Right (int i){    return 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); }}void Print (const std::deque
            
              &ideq){ for (const auto &elem : ideq) { std::cout << elem << "\t"; }}int main (){ std::ios::sync_with_stdio (false); std::deque
             
               ideq{ 5, 13, 2, 25, 7, 17, 20, 8, 4}; Print (ideq); HeapSort (ideq); std::cout << "\n"; Print (ideq); std::cout << std::endl; return 0;}
             
            
           
          
         
        
       
      
     

 

其实我觉得用 forward_list 似乎更为贴切, 但是使用上没有 deque 方便, so......

其间因为有些粗心, 导致了一些小问题, 所以不得不说 VS 的调试能力就是强啊......