C++输出顺序

我编写了下面的程序来实现min heap数据结构，但没有得到预期的输出。C++输出顺序

#include <iostream> 
#include <iomanip> 
#include <vector> 

using namespace std; 

class MinHeap 
{ 
    vector<int> heap; 
    int size; 

public: 
    MinHeap() 
    { 
     //cout<<"asc"; 
     size=0; 
    } 

    void insert(int n); 
    void heapify(int i); 
    int extract_min(); 

    int get_size() 
    { 
     return size; 
    } 
}; 

void MinHeap::insert(int n) 
{ 
    int i=size, parent; 
    parent=(i-1)/2; 
    heap.push_back(n); 
    size++; 

    while(i>0) 
    { 
     if(heap[i]<heap[parent]) 
     { 
      swap(heap[i], heap[parent]);    
     } 
     else 
      break; 
     i=parent; 
     parent=(i-1)/2; 
    } 
} 

void MinHeap::heapify(int i) 
{ 
    int left=2*i+1, right=2*i+2, min_index=i; 

    if(left<size && heap[left]<heap[min_index]) 
     min_index=left; 
    if(right<size && heap[right]<heap[min_index]) 
     min_index=right; 
    if(min_index!=i) 
    { 
     swap(heap[i], heap[min_index]); 
     heapify(min_index); 
    } 
} 

int MinHeap::extract_min() 
{ 
    int i=size-1, temp; 

    if(i>=0) 
    { 
     temp=heap[0]; 
     heap[0]=heap[i]; 
     size--; 
     heapify(0); 

    } 
    return temp; 
} 



int main() 
{ 

    int n, i, last=0, val, j; 
    MinHeap h; 
    h.insert(10); 
    h.insert(5); 
    h.insert(7); 
    h.insert(1); 
    cout<<h.extract_min()<<" "<<h.extract_min()<<" "<<h.extract_min()<<" "<<h.extract_min(); 
    // cout<<h.extract_min()<<"\n"; 
    // cout<<h.extract_min()<<"\n"; 

    return 0; 
}

输出：10 7 5 1

预期输出：1 5 7 10

但是我得到当我打印他们在不同的线路（如我在注释行已经完成了预期的输出，只是主要在return 0以上）。

对不起，如果我错过了一些微不足道的东西。

来源

2016-12-19 shiva

还要注意的是标准库中已经有一些功能来管理堆，如['标准:: make_heap'（http://en.cppreference.com/w/cpp/algorithm/make_heap ）。 – Holt

谢谢。它说它构造了'Max Heap'，该库用于'Min Heap'（或者我应该提供合适的'comp'函数作为参数）？ – shiva

你应该提供一个合适的'comp'（例如'std :: greater '）。 – Holt

h.extract_min()明显改变变量h。所以，在这里你有一个语句中的同一个变量的多个变化。不幸的是，C++标准没有在语句中指定执行顺序，因此，对于h.extract_min()的不同调用不一定以从左到右的方式执行（实际上，您有从右到左的顺序，但它只是运气）。

为了具有正确的输出和可读的代码，可以考虑使用循环：

for (int i = 0; i < 4; ++i) { 
    cout << h.extract_min() << ' '; 
}

来源

2016-12-19 10:04:29 alexeykuzmin0

由此：'C++标准没有在语句中指定执行顺序，您是否指'cout'中的语句？ – shiva

@shiva是的。 ''h.extract_min（）<<“”h.extract_min（）<<“”<< h.extract_min（）<<“”<< h.extract_min（）'是一个语句，其中包含多个函数调用和他们之间的几个'<<'运算符。所有函数调用都可以按任意顺序执行。 – alexeykuzmin0

几乎所有的C++运算符（包括函数参数评价的一个函数调用表达式中的顺序的操作数的计算顺序和在任何表达式中对子表达的评估顺序）是未指定的。编译器可以按任何顺序评估操作数，并且可以在再次评估同一个表达式时选择另一个顺序。

http://en.cppreference.com/w/cpp/language/eval_order

来源

2016-12-19 10:13:29

回答

相关问题