-1

当左右子节点相等且小于父节点时，我应该怎么做才能从最小堆中删除一个值。例如，我的最小堆的根上有一个值 0 并且想要删除它。我将用向量的最后一个元素交换 0（值 = 12），之后，我需要运行将向量再次转换为最小堆的函数（min-heapfy），但在我的示例中，我交换了 0有 12，现在 12 在根上，很快就会返回 0。我必须将 12 与左孩子 (1) 或右孩子 (1) 交换，我怎么知道这个数字 1 中哪个先输入到向量中？

#include <stdio.h>
#include <stdlib.h>

int left(int i){
    return 2*i;
}

int right(int i){
    return 2*i +1;
}

void swap_pos(int *vi, int *vm){
    int aux;
    aux = *vi;
    *vi = *vm;
    *vm = aux;
}

void heapify(int *v, int i,int heap_size){ 
    int l,r,menor_ind = i;
    l = left(i); 
    r = right(i); 
    if(l<=heap_size && v[l]<v[i]) menor_ind = l;
    if(r<=heap_size && v[r]<v[menor_ind]) menor_ind = r;
    if(menor_ind!= i){
        swap_pos(&v[i],&v[menor_ind]);
        heapify(v,menor_ind,heap_size);
    }
}

void build_min_heap(int v[],int heap_size){
    int i;
    for(i=heap_size/2; i>=1; i--){
        heapify(v,i,heap_size);
    }
}

int extract(int *v, int *heap_size){
    int ret = v[1];
    if(*heap_size==0) return -1;// erro
    swap_pos(&v[*heap_size],&v[1]); // swap root with the last element
    (*heap_size)--;
    heapify(v,1,*heap_size);
    return ret;
}

void heap_sort(int *v, int *heap_size){
    while(*heap_size>=2){
        swap_pos(&v[1],&v[*heap_size]);
        (*heap_size)--;
        heapify(v,1,*heap_size);
    }
}

int main(void){
    int heap_size = 9;
    int i, v[] = {-1,6,12,3,1,5,0,1,9,7};
    build_min_heap(v,heap_size);
    printf("%d\n",extract(v,&heap_size));
    //heap_sort(v,&heap_size);
    for(i=1; i<=heap_size; i++){
        printf("%d ",v[i]);
    }
    return 0;
}
4

1 回答 1

0

就堆而言，1并且1是平等的。1（事实上​​，这通常是正确的。）因此，哪个成为新根并不重要。将12在堆中渗透，直到找到休息的地方，可能在边缘，但不一定。没有什么需要它回到原来的地方，而且很可能不会。

为什么您认为您提供的代码不正确？

于 2013-10-17T04:24:27.267 回答