0

抱歉，这里是初学者编码器。我在网上找到了一个最小堆实现并将其放入我的加权图中。

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

可能还有一些其他的。有什么理由会这样吗？

4

1 回答 1

0

检查您的 heapifydown 逻辑。你不是在比较父母的体重和孩子的体重你只是盲目地交换。你只是在比较孩子的体重。

于 2014-11-24T22:58:32.773 回答