ヒープソートで行われた比較の回数を数える

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

あなたは比較を行う前にカウンターをインクリメントしたいが。

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

} 

条件がtrueの場合にのみ、カウンタをインクリメント：あなたのshiftRight方法から、このコードを考えてみましょう。 pq_keys[swpIdx] >= pq_keys[leftChild]の場合、それを数えずに比較しました。あなたは比較をカウントし、他の2つの場所で同じことを行う必要があり

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

} 

：あなたはあなたのようにコードを変更する必要があるカウンタをインクリメント、その後、比較を行います。

Answer 2

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(); 
    }