最小堆插入函数

Question

这是最小堆的插入函数。我不明白为什么它不起作用。

void insertHeapMin(Heap* h, int x){
if(isFull(h)){
    printf("heap is full\n");
    return;
}
for(i=0; i<h->size;i++) //I don't wan't to insert one number more than once; 
{
    if(x==h->data[i]) return;
}
int pos = h->size;
h->data[pos]=x;
while(pos>0){
    int parentPos = (pos-1)/2; 
    if (h->data[pos] < h->data[parentPos]){
        int temp = h->data[pos];
        h->data[pos] = h->data[parentPos];
        h->data[parentPos] = temp;
        pos = parentPos;
    } else
        break;
}
h->size++;
}

主要的：

int a[] ={4,3,6,4,5};
size_t n = sizeof(a)/sizeof(a[0]);
Heap h;
initHeap(&h,100);
int i;
for(i=0;i<n;i++){
    insertHeapMin(&h, a[i]);
}
for(i=0;i<n;i++){
    printf("%d ",h.data[i]);
}
printf("\n");

它返回3 4 6 5 1666986547。我真的看不出哪里出错了，当我修改max-heap的插入函数时它完美地工作，当没有重复元素时，仍然不知道如何修复for用于重复元素的循环。

Answer 1

一、垃圾值1666986547从何而来？此数组元素未初始化，因为您有重复的元素，在插入之前将其过滤掉。原始数组的长度为 5，堆数组的长度仅为 4。h.size打印时使用堆大小作为限制。

二、为什么堆数组没有排序？堆数组只是部分排序：它们满足任何节点的父节点不得大于其任何子节点的条件。你的平面阵列

3 4 6 5

看起来像这样的堆：

    3
  4   6
5

满足堆不变量，但未确定每行元素的顺序。如果要对数组进行排序，请弹出顶部元素，直到堆为空。移除 to 元素后，用较小的孩子反复填充间隙，直到碰到一片叶子。在您的堆中，它看起来像这样：

    3           4           5           6
  4   6       5   6       6*   
5

在第 3 步中，移动了 6 个 (*)，因为平面阵列中不能有间隙。

我评论说，在插入之前对重复项进行线性搜索会降低堆的性能。每次从顶部移除和每次插入都将访问 log(n) 个元素 - log(n) 是 n 个元素的堆的深度。通过首先进行线性搜索，您可以得到 n log(n)。

相反，插入所有元素（如果您有很多重复项，则以增加空间为代价）。移除顶部元素后，重新堆化堆，直到新的顶部元素不同。在大多数情况下，这应该会为您提供更好的性能。