二叉堆中key的作用

Question

我使用 class 在我的课本中获得了这个二叉堆实现代码。但是我不明白 key 在构建堆中的必要性。

#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
        }
    }
}

Key和map在MinHeap中的作用是什么？

Answer 1

在你的情况下，密钥什么都不做，它甚至出现在评论中：

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

还要注意，所有的键都分配给了MAXREAL，基本上键可以用到keep the heap property。

在您的情况下，这不能称为堆。因为 Heapify 过程没有被调用，并且没有对数组中顺序的假设。基本上这意味着您的数据集中没有特定顺序，因此这不是最小堆。

同样在堆中，元素从位置 0 开始存储 - 这是最小值。

看起来代码不完整或不正确

Answer 2

在这里，您的堆树将基于 key 值构建。

例如：这里红框内的值为key，圆圈内的值为data 因为，它是一个最小堆，所以它建立在 key 的值之上。根的 key 将小于它的 child.

二叉堆中key的作用

Function of key in Binary Heap

c++

algorithm

binary-heap

data-structures