1

I'm trying to work with this heap. I'm inserting a few random numbers then removing them to make sure my heap works. The problem is when I'm removing them I get duplicate numbers that shouldn't exist in the Heap. Pretty much I'll insert the following numbers and get back in return: 5 2 10 10 for some reason.

My main looks like this:

#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;
}

And my Heap looks like this:

#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

I'm pretty sure the problem isn't when I'm inserting into my Heap but when I'm removing it.

EDIT I changed my _siftDown a bit - now the numbers show up 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 + 1or 2*parent + 2，没有溢出，因为parent应该总是>= 0，那总是积极的 ~> 条件满足。

您需要检查是否要交换heapData[parent]and heapData[child]，因此条件应该是if (heapData[parent] < heapData[child])。

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

您正在交换 indexchild和处的元素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 有问题。您与左孩子一起筛选并不总是正确的。

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

您可以使用以下函数而不是实现自己的堆：

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

您可以在算法标题中找到它们

于 2013-05-09T20:08:25.237 回答
0 
heapData[0] = heapData[currSize];

Here you should not use heapData[currSize] otherwise you are copying the last elemnt of the heap to the top.

For example after removing 5 from the heap currSize is 3 and you do

heapData[0] = heapData[3];

which will create a duplicate of 10 at heapData[0].

于 2013-05-09T20:09:09.017 回答
-1

不仔细查看您的代码 您是否意识到测试从未初始化？

int test; //initialization should happen here
while(inlist.remove(test))
    cout << test << endl;

我也不明白 Heap::remove(dataOut) 参数的目的是什么。它会不同于 Heap::remove(void) 吗？

于 2013-05-09T20:06:10.827 回答