Функция ключа в двоичной кучи

Я получил этот код реализации 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?

0

Решение

Здесь ваше дерево кучи будет построено на основе key значение. Например: здесь значение внутри красного поля - & lt; code & gt; key & lt; / code & gt; и значение внутри cirle является & lt; code & data & lt; / code & gt;

Например: здесь значение внутри красного поля key и значение внутри круга data
Так как, это минимальная куча, поэтому она основана на значении key, Корнеплоды key будет меньше, чем это ребенок.

0

Другие решения

В вашем случае ключ ничего не делает, он даже представлен в комментарии:

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

Также обратите внимание, что все ключи назначены MAXREAL в основном ключ может быть использован для того, чтобы сохранить свойство кучи.

В вашем случае это нельзя назвать кучей. так как Heapify Процесс не вызывается, и нет никаких предположений о порядке в массиве. По сути это означает, что в вашем наборе данных нет определенного порядка, так что это не Минимальная куча.

Также в куче элементы хранятся из местоположения 0 — что является минимумом.

Похоже, код неполный или неверный

0

По вопросам рекламы [email protected]