Wie implementiert man einen max-heap

Habe ich den code zum erstellen eines max-Heaps, aber es hält bei der Rückkehr das gleiche array gebe ich es. Ich bin sicher, dass es ein geringfügiger Fehler, aber ich kann nicht scheinen, um es herauszufinden. Jede Hilfe ist willkommen.

Kompilierbare Beispiel-code:

#include <iostream>
#include <cmath>

class Heaparr {
public:
    Heaparr();
    void insert(int da);
    int getLeft(int i) { return 2 * i; }
    int getRight(int i) { return (2 * i) + 1; }
    int getParent(int i) { return i / 2; }
    int getMax() { return maxHeap[0]; }
    void print();
    void reheap(int num);
    void makeArray();
    void Build_Max_Heap(int maxHeap[], int heap_size);
    void Max_Heapify(int heapArray[], int i, int heap_size);
    void heapSort(int heapArray[]);

private:
    int size;
    int* maxHeap;
    int index;
    int i;
};

Heaparr::Heaparr() {
    maxHeap = nullptr;
    size = 0;
}

void Heaparr::insert(int da) {
    size++;
    int* tmp = new int[size];

    for (int i = 0; i < size - 1; i++) {
        tmp[i] = maxHeap[i];
    }

    tmp[size - 1] = da;
    delete[] maxHeap;
    maxHeap = tmp;
}

void Heaparr::heapSort(int maxHeap[]) {
    int heap_size = size;
    int n = size;
    int temp;

    Build_Max_Heap(maxHeap, heap_size);

    for (int i = n - 1; i >= 1; i--) {
        temp = maxHeap[0];
        maxHeap[0] = maxHeap[i];
        maxHeap[i] = temp;

        heap_size = heap_size - 1;
        Max_Heapify(maxHeap, 0, heap_size);
    }

    for (int i = 0; i < 8; i++) {
        std::cout << maxHeap[i] << std::endl;
    }
}

void Heaparr::Build_Max_Heap(int maxHeap[], int heap_size) {
    int n = size;
    for (int i = floor((n - 1) / 2); i >= 0; i--) {
        Max_Heapify(maxHeap, i, heap_size);
    }
    return;
}

void Heaparr::Max_Heapify(int heapArray[], int i, int heap_size) {
    //int n = size;
    int largest = 0;
    int l = getLeft(i);
    int r = getRight(i);

    if ((l <= heap_size) && (heapArray[l] > heapArray[i])) {
        largest = l;
    } else {
        largest = i;
    }

    if ((r <= heap_size) && (heapArray[r] > heapArray[largest])) {
        largest = r;
    }

    int temp;
    if (largest != i) {
        temp = heapArray[i];
        heapArray[i] = heapArray[largest];
        heapArray[largest] = temp;

        Max_Heapify(heapArray, largest, heap_size);
    }
    return;
}

int main(int argc, char* argv[]) {
    int hArray[8] = {5, 99, 32, 4, 1, 12, 15, 8};
    Heaparr t;
    t.heapSort(hArray);
    for (auto v : hArray) {
        std::cout << v << ", ";
    }
    std::cout << std::endl;
}

Haben Sie ging durch den code in einem debugger? Was war das Ergebnis?
Statt zu schreiben Ihre eigenen Haufen, warum nicht make_heap? cplusplus.com/reference/algorithm/make_heap
Die .h-Datei und die fehlenden Funktionen getLeft und getRight wäre gut zu haben. Eine kompilierbare Beispiel wäre toll.
Ich fügte hinzu, die .h-Datei
In Ihrer Funktion einfügen, nachdem Sie "da" als das Letzte element in temp, fügen Sie nach oben in die richtige Stellung. Da, das ist max. heap, müssen Sie vergleichen mit Eltern bei maxHeap[Größe/2] und wenn größere tauschen Sie die beiden. Ich sehe nicht, wie Sie dies tun.

InformationsquelleAutor user3316874 | 2014-07-31

arrays c++heap

Machte ich einige Feste der code (ich versuche nicht zu viel verändert, der ursprüngliche code):

Die getLeft, getRight und getParent Formeln waren falsch (Beispiel: wenn Sie i == 0 Kinder müssen 1 und 2 und mit dem code sind 0 und 1. Der return-Typ war auch falsch, sollte int (array-index).
Erhalten Sie in allen Methoden eine int[] außer in insert und die member variable sind double[] änderten, um int[], wenn Sie sich wieder alle zu Doppel -
Mit std::swap für swap-Werte in das array.
Hinzufügen die Länge des Arrays zu heapSort (innerhalb der Methode, diese info ist verloren, übergeben werden müssen, die durch den parameter).

Hinweise:

Ich nicht sehen, wo Sie verwenden Sie die member-variable maxHeap, weil alle Methoden, außer getMax und insert mit dem array-parameter übergeben und nicht die variable (vielleicht sollte man die Initialisierung im Konstruktor oder in heapSort Methode.
Versuchen std::vector statt C Array

Code:

#include <iostream>
#include <cmath>

class Heaparr {
public:
    Heaparr();
    void insert(int da);
    int getLeft(int i) { return 2 * i + 1; }
    int getRight(int i) { return 2 * i + 2; }
    int getParent(int i) { return (i - 1) / 2; }
    int getMax() { return maxHeap[0]; }
    void print();
    void reheap(int num);
    void makeArray();
    void Build_Max_Heap(int heapArray[], int heap_size);
    void Max_Heapify(int heapArray[], int i, int heap_size);
    void heapSort(int heapArray[], int heap_size);

private:
    int size;
    int* maxHeap;
    int index;
    int i;
};

Heaparr::Heaparr() {
    maxHeap = nullptr;
    size = 0;
}

void Heaparr::insert(int da) {
    size++;
    int* tmp = new int[size];

    for (int i = 0; i < size - 1; i++) {
        tmp[i] = maxHeap[i];
    }

    tmp[size - 1] = da;
    delete[] maxHeap;
    maxHeap = tmp;
}

void Heaparr::heapSort(int heapArray[], int heap_size) {
    size = heap_size;
    int n = size;
    Build_Max_Heap(heapArray, heap_size);

    for (int i = n - 1; i >= 1; i--) {
        std::swap(heapArray[0], heapArray[i]);
        heap_size = heap_size - 1;
        Max_Heapify(heapArray, 0, heap_size);
    }
}

void Heaparr::Build_Max_Heap(int heapArray[], int heap_size) {
    int n = size;
    for (int i = floor((n - 1) / 2); i >= 0; i--) {
        Max_Heapify(heapArray, i, heap_size);
    }
    return;
}

void Heaparr::Max_Heapify(int heapArray[], int i, int heap_size) {
    //int n = size;
    int largest = 0;
    int l = getLeft(i);
    int r = getRight(i);

    if ((l < heap_size) && (heapArray[l] < heapArray[i])) {
        largest = l;
    } else {
        largest = i;
    }

    if ((r < heap_size) && (heapArray[r] < heapArray[largest])) {
        largest = r;
    }

    if (largest != i) {
        std::swap(heapArray[i], heapArray[largest]);
        Max_Heapify(heapArray, largest, heap_size);
    }
    return;
}

int main(int argc, char* argv[]) {
    int hArray[8] = {5, 99, 32, 4, 1, 12, 15, 8};

    Heaparr t;
    t.heapSort(hArray, sizeof(hArray)/sizeof(hArray[0]));
    for (auto v : hArray) {
        std::cout << v << ", ";
    }
    std::cout << std::endl;
    return 0;
}

Ausgabe:
99, 32, 15, 12, 8, 5, 4, 1,

Getestet GCC 4.9.0 mit C++11

InformationsquelleAutor NetVipeC

Wenn Sie bereit sind, zu prüfen, alternative Implementierungen, dann ist hier eine:

#define MIN_TYPE  0
#define MAX_TYPE ~0

template<int TYPE,typename ITEM>
class Heap
{
public:
    Heap(int iMaxNumOfItems);
    virtual ~Heap();
public:
    bool AddItem(ITEM*  pItem);
    bool GetBest(ITEM** pItem);
protected:
    int  BestOfTwo(int i,int j);
    void SwapItems(int i,int j);
protected:
    ITEM** m_aItems;
    int    m_iMaxNumOfItems;
    int    m_iCurrNumOfItems;
};

template<int TYPE,typename ITEM>
Heap<TYPE,ITEM>::Heap(int iMaxNumOfItems)
{
    m_iCurrNumOfItems = 0;
    m_iMaxNumOfItems = iMaxNumOfItems;
    m_aItems = new ITEM*[m_iMaxNumOfItems];
    if (!m_aItems)
        throw "Insufficient Memory";
}

template<int TYPE,typename ITEM>
Heap<TYPE,ITEM>::~Heap()
{
    delete[] m_aItems;
}

template<int TYPE,typename ITEM>
bool Heap<TYPE,ITEM>::AddItem(ITEM* pItem)
{
    if (m_iCurrNumOfItems == m_iMaxNumOfItems)
        return false;

    m_aItems[m_iCurrNumOfItems] = pItem;

    for (int i=m_iCurrNumOfItems,j=(i+1)/2-1; j>=0; i=j,j=(i+1)/2-1)
    {
        if (BestOfTwo(i,j) == i)
            SwapItems(i,j);
        else
            break;
    }

    m_iCurrNumOfItems++;

    return true;
}

template<int TYPE,typename ITEM>
bool Heap<TYPE,ITEM>::GetBest(ITEM** pItem)
{
    if (m_iCurrNumOfItems == 0)
        return false;

    m_iCurrNumOfItems--;

    *pItem = m_aItems[0];
    m_aItems[0] = m_aItems[m_iCurrNumOfItems];

    for (int i=0,j=(i+1)*2-1; j<m_iCurrNumOfItems; i=j,j=(i+1)*2-1)
    {
        if (j+1 < m_iCurrNumOfItems)
            j = BestOfTwo(j,j+1);
        if (BestOfTwo(i,j) == j)
            SwapItems(i,j);
        else
            break;
    }

    return true;
}

template<int TYPE,typename ITEM>
int Heap<TYPE,ITEM>::BestOfTwo(int i,int j)
{
    switch (TYPE)
    {
        case MIN_TYPE: return *m_aItems[i]<*m_aItems[j]? i:j;
        case MAX_TYPE: return *m_aItems[i]>*m_aItems[j]? i:j;
    }
    throw "Illegal Type";
}

template<int TYPE,typename ITEM>
void Heap<TYPE,ITEM>::SwapItems(int i,int j)
{
    ITEM* pItem = m_aItems[i];
    m_aItems[i] = m_aItems[j];
    m_aItems[j] = pItem;
}

Und hier ist ein Beispiel:

typedef int ITEM;
#define SIZE 1000
#define RANGE 100

void test()
{
    ITEM* pItem;
    ITEM aArray[SIZE];
    Heap<MIN_TYPE,ITEM> cHeap(SIZE);

    srand((unsigned int)time(NULL));

    for (int i=0; i<SIZE; i++)
    {
        aArray[i] = rand()%RANGE;
        cHeap.AddItem(aArray+i);
    }

    for (int i=0; i<SIZE; i++)
    {
        cHeap.GetBest(&pItem);
        printf("%d\n",*pItem);
    }
}

Beschreibung:

Diese Klasse speichert bis zu N Elemente des Typs T
Es ermöglicht das hinzufügen eines Elements oder die Extraktion die beste Position
Unterstützten Operationen werden durchgeführt bei O(log(n)), wo n ist die aktuelle Anzahl der Elemente

Bemerkungen:

T ist bestimmt bei der Deklaration und N ist bestimmt bei der Initialisierung
Sinne von "best", entweder minimal oder maximal ist, ist bestimmt bei der Deklaration
Zur Unterstützung Heap<MIN,T> und Heap<MAX,T> eine der folgenden Optionen muss tragfähig sein:
1. bool operator<(T,T) und bool operator>(T,T)
2. bool T::operator<(T) und bool T::operator>(T)
3. T::operator P(), wo P ist eine Art, für die eine der oben genannten Optionen ist möglich

InformationsquelleAutor barak manos

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.