计算 Heapsort 中完成的比较次数

Question

我正在尝试计算堆排序算法完成的比较次数。我的代码是基于优先队列的，我想知道我应该把计数器放在哪里。这是我所拥有的但是当我尝试打印计数器时它显示零计数，我做错了什么？谢谢。

这里是 heapbuild 函数：

#include<iostream>

vector<int> pq_keys;
void buildHeap()
{
int size = pq_keys.size();
int midIdx = (size -2)/2;
while (midIdx >= 0)
{      
    shiftRight(midIdx, size-1);     
    --midIdx;
}

这是进行比较的函数：

int shiftRight(int low, int high)
{
  int root = low;
  int counter=0;
  while ((root*2)+1 <= high)
    {
      int leftChild = (root * 2) + 1;
      int rightChild = leftChild + 1;
      int swapIdx = root;
      if (pq_keys[swapIdx] < pq_keys[leftChild])
    {
      counter++;
      cout<<counter;
      swapIdx = leftChild;

    }
    /*If right child exists check if it is less than current root*/
    if ((rightChild <= high) && (pq_keys[swapIdx] < pq_keys[rightChild]))
    {
    counter++;
    swapIdx = rightChild;    
    }
    /*Make the biggest element of root, left and right child the root*/
    if (swapIdx != root)
    { 
    counter++;
    int tmp = pq_keys[root];
    pq_keys[root] = pq_keys[swapIdx];
    pq_keys[swapIdx] = tmp;
    root = swapIdx;
    }
    else
    {
        break;
    }
}

return counter;

}

Answer 1

class LessPredicate 
{
  size_t callCount_ = 0;

  temlate<class T> 
  bool compare(const T& l, conct T& r)
  {
     return l < r; // or other logic
  }
public:
  size_t CallTimes() const { return callCount_; }
  temlate<class T> 
  bool operator() (const T& l, conct T& r)
  {
    ++callCount_;
    return compare(l, r);
  }
};



   int main() 
   {
     LessPredicate less;
     ...// use it like less(a, b) instead a < b;
     auto compareCount = less.CallTimes();
   }

Answer 2

您想在进行比较之前递增计数器。考虑这段代码，来自您的 shiftRight 方法：

if (pq_keys[swapIdx] < pq_keys[leftChild])
{
  counter++;
  cout<<counter;
  swapIdx = leftChild;

}

如果条件为真，那只会增加计数器。如果pq_keys[swpIdx] >= pq_keys[leftChild]，那么你就做了比较，没有算进去。您需要将代码更改为：

counter++;
if (pq_keys[swapIdx] < pq_keys[leftChild])
{
  cout<<counter;
  swapIdx = leftChild;

}

你需要在其他两个计算比较的地方做同样的事情：增加计数器，然后做比较。

计算 Heapsort 中完成的比较次数

Counting the number of comparisons done in Heapsort

c++

sorting

heap

priority-queue