Funktion des Schlüssels in binärem Heap

Question

Ich habe diesen Binary Heap-Implementierungscode in meinem Lehrbuch mit Klasse. Aber ich verstehe nicht die Notwendigkeit, einen Haufen zu bauen.

#define MAXREAL 999999.0 

class HeapItem 
{ 
    public: 
    int data; //actual data that is stored 
    float key; //key value of the data, heap is constructed based on key 
}; 
class MinHeap 
{ 
    public: 
    HeapItem * A; //stores heap items, e.g., nodes 
    int heapLength; 
    int * map; 

    MinHeap() //constructor 
    { 
     A = new HeapItem[MAX_HEAP_SIZE]; 
     map = new int[MAX_HEAP_SIZE]; 
     heapLength = 0; 
    } 
//Fills the heap with an array of integers 
//key values do not maintain heap property 
//May be used in some algorithms such as dijkstra's shortest path 
    void initialize(int v[], int n) 
    { 
     heapLength = n; 
     for (int i = 0; i<n; i++) //nodes are stored from index 1 instead of 0 in the heap 
     { 
      A[i + 1].data = v[i]; 
      A[i + 1].key = MAXREAL; 
      map[v[i]] = i + 1; //map tracks which vertex is stored at which heap node 
     } 
    } 
} 

Was ist die Funktion von Schlüssel und Karte im MinHeap?

Answer 1

Hier finden Sie Ihre Haufen Baum auf der Basis von key Wert bauen sein.

Zum Beispiel: hier Wert innerhalb der roten Box ist key und Wert innerhalb cirle ist data Da es sich um einen min Haufen, so dass er auf dem Wert der key bauen wird. Root's key wird weniger als sein Kind sein.

Answer 2

In Ihrem Fall ist der Schlüssel nichts tut, ist es auch in einem Kommentar präsentiert:

//key values do not maintain heap property 
//May be used in some algorithms such as dijkstra's shortest path 

Beachten Sie auch, dass alle Schlüssel zu MAXREAL im Grunde kann der Schlüssel zugeordnet sind, um keep the heap property verwendet werden.

In Ihrem Fall kann dies nicht als Heap bezeichnet werden. seit der Heapify Prozess wird nicht aufgerufen, und es gibt keine Annahme in der Reihenfolge im Array. Grundsätzlich bedeutet dies, dass es in Ihrem Dataset keine bestimmte Reihenfolge gibt, sodass dies kein minimaler Heap ist.

Auch in einem Heap-Elemente werden von Ort 0 gespeichert - das ist das Minimum.

Es ist wie der Code aussieht, ist entweder unvollständig oder fehlerhaft