首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >Min删除Min坏了吗?

Min删除Min坏了吗?
EN

Stack Overflow用户
提问于 2013-04-15 18:35:23
回答 1查看 929关注 0票数 0

抱歉,初学者来了。我在网上找到了一个最小堆实现,并将其放入我的加权图中。

代码语言:javascript
运行
复制
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 6868 7711 8723 8942 9040 9741 9961 11538 11942 12316 12382 12859 14604 14771 15141 15724 17035 17421 17473 18467 19264 18716 19169 19718 19912 21726 22190 22648 23281 23811 24464 25667 20037 26299 26500 25547 16827 26962 27644 19895E 210/代码> 28145 <>代码E 11127529<代码>E 212/代码> 28253 28703 358 30303106 30393 30391 23391 23391 27391 27391 27391 27357 27357 27357

可能还有其他人。有什么原因吗?

EN

回答 1

Stack Overflow用户

发布于 2014-11-24 22:58:32

检查你的堆下逻辑。你不是在把父母的体重和孩子的体重作比较,你只是在盲目地交换。你只是在比较孩子们的体重。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/16022373

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档