1

私はこのヒープで作業しようとしています。いくつかの乱数を挿入してから削除して、ヒープが機能することを確認しています。問題は、それらを削除すると、ヒープに存在してはならない重複した番号が取得されることです。5 2 10 10ほとんどの場合、次の番号を挿入すると、何らかの理由で返されます。

私のメインは次のようになります。

#include <iostream>
#include <fstream>
using namespace std;
#include "heap.h"

int main(void)
{
    Heap<int> inlist(4);
    inlist.insert(5);
    inlist.insert(2);
    inlist.insert(3);
    inlist.insert(10);
    int test;
    while(inlist.remove(test))
        cout << test << endl;
}

そして、私のヒープは次のようになります。

#ifndef HEAP_H
#define HEAP_H

template<typename TYPE>
class Heap
{
    private:
        TYPE* heapData;
        int currSize;
        int capacity;
        void _siftUp(int);
        void _siftDown(int);
        int _leftChildOf(int) const;
        int _parentOf(int) const;

    public:
        Heap(int c = 100);
        ~Heap();
        bool viewMax(TYPE&) const;
        int getCapacity() const;
        int getCurrSize() const;
        bool insert(const TYPE&);
        bool remove(TYPE&);
};

template<typename TYPE>
Heap<TYPE>::Heap(int c = 100)
{
    capacity = 100;
    currSize = 0;
    heapData = new TYPE[capacity];
}

template<typename TYPE>
Heap<TYPE>::~Heap()
{
    delete[] heapData;
    currSize = 0;
    capacity = 0;
}

template<typename TYPE>
bool Heap<TYPE>::insert(const TYPE& dataIn)
{
    bool success = false;
    if(currSize < capacity)
    {
        heapData[currSize] = dataIn;
        _siftUp(currSize);
        currSize++;
        success = true;
    }
    return success;
}

template<typename TYPE>
void Heap<TYPE>::_siftUp(int child)
{
    TYPE temp;
    int parent;
    if(child > 0)
    {
        parent = _parentOf(child);
        if(heapData[child] > heapData[parent])
        {
            temp = heapData[parent];
            heapData[parent] = heapData[child];
            heapData[child] = temp;
            _siftUp(child);
        }
    }
}

template<typename TYPE>
bool Heap<TYPE>::remove(TYPE& dataOut)
{
    bool success = false;
    if(currSize > 0)
    {
        dataOut = heapData[0];
        currSize--;
        heapData[0] = heapData[currSize];
        _siftDown(0);
        success =  true;
    }
    return success;
}

template<typename TYPE>
void Heap<TYPE>::_siftDown(int parent)
{
    TYPE temp;
    int child = _leftChildOf(parent);
    if(child < currSize)
    {
        if((child + 1 < currSize) && (heapData[child] < heapData[child + 1]))
            child++;

        if(child)
        {
            temp = heapData[child];
            heapData[child] = heapData[child + 1];
            heapData[child + 1] = temp;
            _siftDown(child);
        }
    }
}

template<typename TYPE>
int Heap<TYPE>::_leftChildOf(int p) const
{
    return(2 * p + 1);
}

template<typename TYPE>
int Heap<TYPE>::_parentOf(int c) const
{
    return((c - 1) / 2);
}
//**************************************************************************
template<typename TYPE>
int Heap<TYPE>::getCapacity() const
{
    return capacity;
}

template<typename TYPE>
int Heap<TYPE>::getCurrSize() const
{
    return currSize;
}

template<typename TYPE>
bool Heap<TYPE>::viewMax(TYPE& max) const
{
    return false;
}
#endif

ヒープに挿入するときではなく、ヒープを削除するときに問題があると確信しています。

編集_siftDown を少し変更しました-数字が表示されるようになりました5 10 3 2

if(child)
{
    temp = heapData[child];
    heapData[child] = heapData[parent];
    heapData[parent] = temp;
    _siftDown(child);
}
4

5 に答える 5

2

あなた_siftDownは壊れています、

template<typename TYPE>
void Heap<TYPE>::_siftDown(int parent)
{
    TYPE temp;
    int child = _leftChildOf(parent);
    if(child < currSize)
    {
        if((child + 1 < currSize) && (heapData[child] < heapData[child + 1]))
            child++;

        if(child)

調べるってどういうこと？childこの時点で は または のいずれ2*parent + 1か2*parent + 2で、オーバーフローなしで、parent常に である必要があるため>= 0、これは常に正です ~> 条件が満たされています。

heapData[parent]とをスワップするかどうかを確認する必要があるheapData[child]ため、その条件は である必要がありますif (heapData[parent] < heapData[child])。

        {
            temp = heapData[child];
            heapData[child] = heapData[child + 1];
            heapData[child + 1] = temp;

childindexとで要素を交換していますがchild+1、それは間違っています。ここでスワップする必要がheapData[child]ありheapData[parent]ます。

            _siftDown(child);
        }
    }
}

にもエラーがあります_siftUp。

template<typename TYPE>
void Heap<TYPE>::_siftUp(int child)
{
    TYPE temp;
    int parent;
    if(child > 0)
    {
        parent = _parentOf(child);
        if(heapData[child] > heapData[parent])
        {
            temp = heapData[parent];
            heapData[parent] = heapData[child];
            heapData[child] = temp;
            _siftUp(child);
        }
    }
}

再帰呼び出しは_siftUp(parent)でなければなりません。

于 2013-05-09T20:26:39.750 に答える
1

_siftDown に何か問題がある間は、 remove メソッドは適切です。左の子をふるいにかけるとは限りません。

void Heap<TYPE>::_siftDown(int parent)
{
    TYPE temp;
    int left= _leftChildOf(parent);
    int right= _rightChildOf(parent);
    int max= parent;
    if(left< currSize && heapData[left] > heapData[max])
    {
        max= left;
    }
    if(right< currSize && heapData[right] > heapData[max])
    {
        max= right;
    }
    if( max!=parent ) //need to sift down
    {
        temp = heapData[max];
        heapData[max] = heapData[parent];
        heapData[parent] = temp;
        _siftDown(max);
    }
}

}

于 2013-05-09T20:27:15.583 に答える
0 
heapData[0] = heapData[currSize];

ここでは使用しheapData[currSize]ないでください。それ以外の場合は、ヒープの最後の要素を一番上にコピーします。

たとえば5、ヒープから削除した後、あなたはそうしcurrSizeます3

heapData[0] = heapData[3];

10atの複製を作成しheapData[0]ます。

于 2013-05-09T20:09:09.017 に答える
0

独自のヒープを実装する代わりに、次の関数を使用できます。

std::make_heap
std::push_heap
std::pop_heap

それらはアルゴリズムヘッダーで見つけることができます

于 2013-05-09T20:08:25.237 に答える