1

我正在尝试实现自己的 minHeap，但遇到与模板类相关的错误

这是main.cpp：

#include <iostream>
#include"road.h"
#include"region.h"
#include"minHeap.h"

using namespace std;

int main()
{

//    int numCities;
    int numOldRoads;

    cin >> numOldRoads;

    minHeap<int> roadHeap(numOldRoads);

    roadHeap.push(1);
    roadHeap.push(4);
    roadHeap.push(5);
    roadHeap.push(2);
    roadHeap.push(7);
    roadHeap.push(6);
    roadHeap.push(3);
    roadHeap.push(9);
    roadHeap.push(8);

    int temp;

    for(int i = 0; i<numOldRoads; i++){
        temp = roadHeap.top();
        roadHeap.pop();
        cout << temp;
    }

    return 0;
}

这是头文件：

#ifndef MIN_HEAP
#define MIN_HEAP

template<class T>
class minHeap{

public:
    minHeap(int);
    void push(T);
    void pop();
    T top();
    void doubleHeapCap();
    bool isEmpty();

private:
    T *heap;
    int heapSize;
    int capacity;

};

#endif

这是 minHeap 的实现（也在标题中，因为否则它会给我错误）：

#include"minHeap.h"

template<class T>
minHeap<T>::minHeap(int theCapacity = 10){

    if(theCapacity < 1) throw "Capacity must be >=1.";
    capacity = theCapacity;
    heapSize = 0;
    heap = new T[capacity + 1]; //heap [0] is not used

}

template<class T>
void minHeap<T>::push(const T& e){
//inserts e into min heap
    if(heapSize == capacity){ //doubles capacity if Heap is too small
        minHeap.doubleHeapCap;
        capacity *=2;
    }

    int currentNode == ++heapSize;

    while(currentNode != 1 && heap[currentNode/2] > e){
        //bubble up node
        heap[currentNode] = heap[currentNode/2]; //moves parent down
        currentNode /= 2; //moves current node
    }

    heap[currentNode] = e;

}

template<class T>
void minHeap<T>::pop(){
//Deletes smallest element from heap and restructures heap
    if(isEmpty()) throw "Heap is empty. Cannot delete.";

    //deelt smallest element
    heap[1].~T();

    //remove last element from heap
    T lastE = heap[heapSize--];

    //trick down to restructure heap
    int currentNode = 1; //root of heap
    int child = 2; // first child of heap

    while(child <= heapSize){

        //set child to smaller child of currentNode
        if(child < heapSize && heap[child] > heap[child+1]) child++;

        //can we put lastE in currenNode?
        if(lastE >= heap[child]) break; //yes we can

        //no we can't, Obama
        heap[currentNode] = heap[child]; //move child up
        currentNode = child; child *= 2; // move a level down
    }

    //after you finally find one, place the node in the corrent position
    heap[currentNode] = lastE;
}

template<class T>
bool minHeap<T>::isEmpty(){
//says whether or not hear is empty
    if(heapSize == 0) return 1;
    else return 0;
}

template<class T>
void minHeap<T>::doubleHeapCap(){

    int currentcapacity = this->capacity;
    int newCapacity = (this->capacity)*2;
    minHeap *temp;
    T *newHeap;

    //create a new heap with twic the size
    newHeap = new T[newCapacity + 1];

    //copy elements over
    for(int i=0; i<=capacity; i++){
        newHeap[i] = this->heap[i];
    }

    //delete the old heap
    temp = heap;
    heap = newHeap;
    newHeap = 0;

    delete[] temp;
}

这是错误：

In instantiation of 'void minHeap<T>::doubleHeapCap() [with T = int]':
required from 'void minHeap<T>::push(const T&) [with T = int]'
required from here
error: cannot convert 'int*' to 'minHeap<int>*' in assignment|
warning: unused variable 'currentcapacity' [-Wunused-variable]|

我几乎从我的数据结构书中复制了代码并对其进行了修改（这本书显示了最大堆的实现，我对最小堆感兴趣）。

正如你所看到的，我现在对 main 所做的只是打印出我尝试推送到最小堆的整数的升序列表。

我想我不完全理解如何实现模板类函数......

4

1 回答 1

2

在你的类声明中，你有这个：

T *heap;

在doubleHeapCap你有这个：

minHeap *temp;

// code...

temp = heap;

如果T是，int那么您正在尝试将int*( heap)分配给minHeap<int>*( temp)。基本上，也制作temp成 a T*，它应该可以工作。或者你可以完全省去temp并写：

std::swap(heap, newHeap);
delete[] newHeap;
于 2013-07-20T04:09:09.153 回答