Я получил этот код реализации Binary Heap в своем учебнике, используя класс. Но я не понимаю необходимости ключа в построении кучи.
#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
}
}
}
Какова функция ключа и карты в MinHeap?
Здесь ваше дерево кучи будет построено на основе key
значение.
Например: здесь значение внутри красного поля key
и значение внутри круга data
Так как, это минимальная куча, поэтому она основана на значении key
, Корнеплоды key
будет меньше, чем это ребенок.
В вашем случае ключ ничего не делает, он даже представлен в комментарии:
//key values do not maintain heap property
//May be used in some algorithms such as dijkstra's shortest path
Также обратите внимание, что все ключи назначены MAXREAL
в основном ключ может быть использован для того, чтобы сохранить свойство кучи.
В вашем случае это нельзя назвать кучей. так как Heapify
Процесс не вызывается, и нет никаких предположений о порядке в массиве. По сути это означает, что в вашем наборе данных нет определенного порядка, так что это не Минимальная куча.
Также в куче элементы хранятся из местоположения 0 — что является минимумом.
Похоже, код неполный или неверный