buildHeap

Question

によってinsertKeyによってヒープ1を構築し、他によって異なる答えを取得する私はちょうど分ヒープを構築しようとしましたが、私は、配列の中に、ヒープ

方法1つのインサート要素を構築するための別の答えを取得してからビルドを呼び出しています内部ノード上でminHeapifyを適用するminheapメソッド。

方法2は、配列がminheapプロパティのあとに続くかどうかをチェックすることで、要素をヒープに直接挿入します。

両方の答えが正しいと思いますが、いくつかのテストケースが1つの注文を示していて、ansが異なる場合は大丈夫です。

#include<iostream> 
#include<cmath> 
#include<vector> 
using namespace std; 
int leftChild(int i) 
{ 
    return (2*i+1); 
} 
int rightChild(int i) 
{ 
    return (2*i+2); 
} 
int parent(int i) 
{ 
    return ((i-1)/2); 
} 
void minHeapify(vector<int> &a,int i) 
{ 
    int smallest = i; 
    int l = leftChild(i); 
    int r = rightChild(i); 
    if(l < a.size() && a[l] < a[i]) 
     smallest = l; 
    if(r < a.size() && a[r] < a[smallest]) 
     smallest = r; 
    if(smallest != i) 
    { 
     swap(a[smallest],a[i]); 
     minHeapify(a,smallest); 
    } 
} 
void buildMinHeap(vector<int> &a) 
{ 
    for(int i = a.size()/2 - 1 ; i >= 0 ; i--) 
     minHeapify(a,i); 
} 
void insertKey(vector<int> &b,int new_val,int* n) 
{ 
    *n = *n + 1; 
    int i = *n - 1; 
    b[i] = new_val; 
    while(i!=0 && b[i] < b[parent(i)]) 
    { 
     swap(b[i],b[parent(i)]); 
     i = parent(i); 
    } 
} 
void printline() 
{ 
    cout<<"********************************************************************"<<endl; 
} 
int main() 
{ 
    cout<<"Enter the elements in the array for building a min heap"<<endl; 
    vector<int> a; 
    a.push_back(2); 
    a.push_back(16); 
    a.push_back(74); 
    a.push_back(58); 
    a.push_back(36); 
    a.push_back(4); 
    a.push_back(28); 
    a.push_back(15); 
    a.push_back(35); 
    a.push_back(82); 
    a.push_back(6); 

    //One thing you can do is make a normal array and build a heap out of it in O(n) time 
    buildMinHeap(a); 
    for(int i=0;i<a.size();i++) 
     cout<<a[i]<<" "; 
    cout<<endl<<endl; 
    printline(); 

    //Or second method is insert in a way such that it is always inserted in a form of heap. 
    vector<int> b(10000); 
    int heapsize = 0; 
    insertKey(b,2,&heapsize); 
    insertKey(b,16,&heapsize); 
    insertKey(b,74,&heapsize); 
    insertKey(b,58,&heapsize); 
    insertKey(b,36,&heapsize); 
    insertKey(b,4,&heapsize); 
    insertKey(b,28,&heapsize); 
    insertKey(b,15,&heapsize); 
    insertKey(b,35,&heapsize); 
    insertKey(b,82,&heapsize); 
    insertKey(b,6,&heapsize); 
    for(int i=0;i<heapsize;i++) 
     cout<<b[i]<<" "; 
} 

min_heap関数を使用してチェックし、両方の回答から最小ヒープを構築しました。 min_heap（a.begin（）、a.end（）、myComparator（））は、method1およびmin_heap（b.begin（）、b.end（）、myComparator（））によって生成されたansと同じansを返します。方法2によって。だから私はちょうどこの事は大丈夫です確認したいと思った???

Answer 1

ヒープの場合、基本となるデータ構造に保存される要素の順序は重要ではありません。

最小ヒープからのポップされた値が昇順であること、つまりルート要素が常に最小であることを確認する必要があります。

両方の構造にtop()とpop()メソッドを追加します。 top()は単にルート要素の値を返し、pop()はルート要素を消去し、ヒープから適切な要素に置き換えます。

次のコードは、要素を同じ順序で出力する必要があります。

while(heap.size() > 0) 
{ 
std::cout<<heap.top()<<" "; 
heap.pop(); 
} 

コーディング競技会では、彼らは決して下位の構造の順序をチェックしません。あなたはそれらを順番に印刷することになっています。