Мин куча Удалить Мин из строя?

Извините, начинающий кодер здесь.
Я нашел в сети минимальную реализацию кучи и поместил ее в свой взвешенный график.

class Heap : public weightedGraph
{
public: Heap();
~Heap();
void insert(double element);
double deletemin()
{
double min = heap.front();
heap[0] = heap.at(heap.size()-1);
heap.pop_back();
heapifydown(0);
return min;
};

void print();

int size()
{return heap.size();}private:
int left(int parent);
int right(int parent);
int parent(int child);
void heapifyup(int index);
void heapifydown(int index);

private:
vector<double> heap;
};

Heap::Heap() {}

Heap::~Heap()
void Heap::insert(double element)
{
heap.push_back(element);
heapifyup(heap.size()-1);
}

void Heap::heapifyup(int index)
{
while((index>0) && (parent(index) >=0) && (heap[parent(index)] > heap[index]))
{
double tmp = heap[parent(index)];
heap[parent(index)] = heap[index];
heap[index] = tmp;
index = parent(index);
}
}

void Heap::heapifydown(int index)
{
int child = left(index);

if((child > 0) && (right(index) > 0) && (heap[child]>heap[right(index)]))
{
child = right(index);
}
if(child > 0)
{
double tmp = heap[index];
heap[index] = heap[child];
heap[child] = tmp;
heapifydown(child);
}
}

int Heap::left(int parent)
{
int i = ( parent <<1) + 1;
return(i<heap.size()) ? i : - 1;
}

int Heap::right(int parent)
{
int i = ( parent <<1) + 2;
return(i<heap.size()) ? i : - 1;
}

int Heap::parent(int child)
{
if(child != 0)
{
int i = (child - 1) >>1;
return i;
}
return -1;
}

После добавления всех вершин, когда я запускаю deletemin, пока куча не станет пустой, но некоторые вершины не в порядке.

41
153
288
292
491
+778
1842
1869
2995
3035
3902
4664
4827
5436
5447
5705
6334
6868
7711
8723
8942
9040
9741
9894
9961
11478
11538
11942
12316
12382
12859
14604
14771
15141
15724
17035
17421
17673
18467
19264
18716
19169
19718
19912
21726
22190
22648
23281
23811
24464
25667
20037
26299
26500
25547
16827
26962
27644
19895
28145
27529
28253
28703
29358
30106
30333
31322
32391
32662
32757

Там могут быть некоторые другие. Любая причина, почему это будет?

0

Решение

Проверьте свою логику. Вы не сравниваете вес родителей с весом детей
Вы просто обмениваетесь вслепую. Вы сравниваете только вес детей.

0

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector