Получение разных ответов путем построения кучи один с помощью insertKey, а другой с помощью buildHeap
Я просто попытался собрать кучу мин, и я получаю разные ответы для построения кучи
Метод 1 вставляет элементы в массив, а затем вызывает метод построения minheap, который применяет minHeapify к внутренним узлам.
Метод 2 вставляет элементы непосредственно в кучу, проверяя в каждой точке, если массив соответствует свойству minheap или нет.
Оба ответа верны, я думаю, но все ли в порядке, если какой-то тест показывает один порядок, а ответ другой.
#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 из обоих моих ответов. min_heap (a.begin (), a.end (), myComparator ()) возвращает те же ответы, что и метод1, а min_heap (b.begin (), b.end (), myComparator ()) — те же ответы по методике2. Так что я просто хотел подтвердить, хорошо ли это?
Решение
Для кучи порядок элементов, сохраняемых в базовой структуре данных, не важен.
Вы должны убедиться, что извлеченные значения из Min Heap находятся в порядке возрастания, то есть корневой элемент всегда является минимальным.
добавлять top() а также pop() методы обеих ваших структур. top() просто вернет значение корневого элемента и pop() сотрет корневой элемент и заменит его подходящим элементом из кучи.
Следующий код должен печатать элементы в том же порядке.
while(heap.size() > 0)
{
std::cout<<heap.top()<<" ";
heap.pop();
}
Для соревнований по кодированию они никогда не будут проверять порядок базовой структуры. Вы должны распечатать их по порядку.
Другие решения
Других решений пока нет …
detector